Tree width and regular triangulations (Q5939925)

In \textit{Y. Colin de Verdière} [Multiplicities of eigenvalues and tree-width of graphs, J. Comb. Theory, Ser. B 74, 121-146 (1998; Zbl 1027.05064)] the following two definitions are introduced. The family \(\{\Delta_k\mid k\geq 2\}\) of graphs is defined as follows. Subdivide each side of an equilateral triangle, \(S\), into \(k-1\) equal segments. Through the subdivision points, plot the lines parallel to the sides of \(S\). This induces a triangulation of \(S\) into \((k-1)^2\) congruent triangles. Now, \(\Delta_k\) is the graph of the skeleton of this triangulation. Next, the largeur d'arborescence \(\text{la}(G)\) of a graph \(G\) is defined as the smallest natural number \(k\) such that \(G\) is a minor of the Cartesian product \(K_k\square T\) of the complete graph \(K_k\) and some tree \(T\). In the paper of Colin de Verdière it is proved that \(\text{la}(\Delta_k)\) is equal to \(k\). In the present note the author shows by simple and elegant constructions that \(\text{la}(\Delta_k-e)<k\) for each edge \(e\) of \(\Delta_k\), which is then extended to show that \(\text{la}(H)<k\) holds for each minor \(H\) of \(\Delta_k\). This shows that \(\Delta_k\) is a forbidden minor for the class of graphs \(\{G\mid \text{la}(G)<k\}\). In the paper mentioned above, Colin de Verdière introduced a spectral graph invariant \(v_1^K\), where \(K\) can be taken to be either \(R\) or \(C\), and showed that \(v_1^K(G)\leq \text{la}(G)\) for any graph \(G\) and also that \(v_1^K(\Delta_k)=k\). From here the author immediately obtains that \(\Delta_k\) is also a forbidden minor for the class of graphs \(\{G\mid v_1^K(G)<k\}\). At the end, we mention that the author does not deal with the harder, but interesting question whether \(\Delta_k\) is the only forbidden minor for the above-mentioned classes of graphs.