Some connectivity properties for excluded minors of the graph invariant \(\nu(G)\). (English) Zbl 1026.05080
Summary: Let \(\nu(G)\) be the graph invariant introduced by Y. Colin de Verdière [J. Comb. Theory, Ser. B. 74, 121-146 (1998; Zbl 1027.05064)]. Let \(k\geq 0\), and let \(H\) be an excluded minor of the class of graphs \(G\) with \(\nu(G)\leq k\). We show that \(H\) has no vertex cuts of size at most two and that, if \(S\) is a vertex cut of size three of \(H\), then \(G-S\) has two components, and \(S\) is the neighbourhood of a vertex \(v\) and the subgraph induced by \(S\cup \{v\}\) is isomorphic to one of the graphs in a certain collection of six graphs.
Citations:
Zbl 1027.05064References:
| [1] | Colin de Verdière, Y., On a new graph invariant and a criterion of planarity, (Robertson, N.; Seymour, P., Graph Structure Theory. Graph Structure Theory, Contemporary Mathematics, vol. 147 (1993), American Mathematical Society: American Mathematical Society Providence, RI), 137-147 · Zbl 0791.05024 |
| [2] | Colin de Verdière, Y., Multiplicities of eigenvalues and tree-width of graphs, J. Combin. Theory Ser. B., 74, 121-146 (1998) · Zbl 1027.05064 |
| [3] | H. van der Holst, Topological and spectral graph characterizations, Ph.D. Thesis, University of Amsterdam, 1996; H. van der Holst, Topological and spectral graph characterizations, Ph.D. Thesis, University of Amsterdam, 1996 |
| [4] | van der Holst, H., Graph with magnetic Schrödinger operators of low corank, J. Combin. Theory Ser. B., 84, 311-339 (2002) · Zbl 1024.05060 |
| [5] | Kotlov, A., Spectral characterization of tree-width-two graphs, Combinatorica, 20, 1, 147-152 (2000) · Zbl 0980.05043 |
| [6] | Lancaster, P.; Tismenetsky, M., The Theory of Matrices, With Applications (1985), Academic Press: Academic Press Orlando · Zbl 0516.15018 |
| [7] | Robertson, N.; Seymour, P.; Thomas, R., Hadwiger’s conjecture for \(K_6\)-free graphs, Combinatorica, 13, 279-361 (1993) · Zbl 0830.05028 |
| [8] | N. Robertson, P.D. Seymour, Graph minors. XX. Wagner’s conjecture (manuscript); N. Robertson, P.D. Seymour, Graph minors. XX. Wagner’s conjecture (manuscript) · Zbl 1061.05088 |
| [9] | Strang, G., Linear Algebra and Its Applications (1980), Academic Press: Academic Press Orlando · Zbl 0463.15001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
