Matchings and Hadwiger's conjecture
作者： Andreı̆ Kotlov
DOI: 10.1016/S0012-365X(01)00087-5
关键词: Treewidth 、 Conjecture 、 Combinatorics 、 Discrete mathematics 、 Structured program theorem 、 Mathematics 、 Minimal counterexample 、 Graph
摘要: Assuming that a graph G on n vertices is minimal counterexample to Hadwiger's Conjecture χ(G) ≤ η(G), we apply the Edmonds-Gallai Structure Theorem its complement, H, find H has matching of size ⌊n/2⌋. Hence Magyar Tud. Acad. Mat. Kutato Int. Kozl. 8 (1963) 373: ⌈n/2⌉. Further, homeomorphic three-connected graph, and tree width at least four. The same holds for Colin de Verdiere's µ(G) + 1 ≥ χ(G).
elsevier.com
sci-hub.se 参考文章(7)
Casimir Kuratowski, Sur le problème des courbes gauches en Topologie Fundamenta Mathematicae. ,vol. 15, pp. 271- 283 ,(1930) , 10.4064/FM-15-1-271-283
Bjarne Toft, An Investigation of Colour-Critical Graphs with Complements of Low Connectivity Annals of discrete mathematics. ,vol. 3, pp. 279- 287 ,(1978) , 10.1016/S0167-5060(08)70513-2
Neil Robertson, Paul Seymour, Robin Thomas, Hadwiger's conjecture for K6-free graphs Combinatorica. ,vol. 13, pp. 279- 361 ,(1993) , 10.1007/BF01202354
Andrew Kotlov, L�szl� Lov�sz, Santosh Vempala, The Colin de Verdière number and sphere representations of a graph Combinatorica. ,vol. 17, pp. 483- 521 ,(1997) , 10.1007/BF01195002
B. Bollobás, P.A. Catlin, P. Erdös, Hadwiger's Conjecture is True for Almost Every Graph European Journal of Combinatorics. ,vol. 1, pp. 195- 199 ,(1980) , 10.1016/S0195-6698(80)80001-1
Neil Robertson, P.D Seymour, Graph minors. III. Planar tree-width Journal of Combinatorial Theory, Series B. ,vol. 36, pp. 49- 64 ,(1984) , 10.1016/0095-8956(84)90013-3
K. Wagner, Über eine Eigenschaft der ebenen Komplexe Mathematische Annalen. ,vol. 114, pp. 570- 590 ,(1937) , 10.1007/BF01594196