On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture

DOI10.1016/j.jctb.2006.04.004zbMath1107.05034OpenAlexW2135517930MaRDI QIDQ858685

Ken-ichi Kawarabayashi

Publication date: 11 January 2007

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2006.04.004

zbMATH Keywords

contraction-critical graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items

Coloring graphs with forbidden minors, Some recent progress and applications in graph minor theory, Refined List Version of Hadwiger’s Conjecture, Recent progress towards Hadwiger's conjecture, Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor, An improved linear connectivity bound for tournaments to be highly linked, Connectivities for \(k\)-knitted graphs and for minimal counterexamples to Hadwiger's conjecture, Hadwiger’s Conjecture, Linear connectivity forces large complete bipartite minors, Minimum degree condition for a graph to be knitted, Connectivity and choosability of graphs with no \(K_t\) minor, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Linear connectivity forces large complete bipartite minors
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• The four-colour theorem
• An improved linear edge bound for graph linkages
• Graph minors. XIII: The disjoint paths problem
• Vertex-disjoint cycles containing specified edges
• Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
• Non-zero disjoint cycles in highly connected group labelled graphs
• Über trennende Eckenmengen in homomorphiekritischen Graphen
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• On separating sets of edges in contraction-critical graphs
• Graphs with forbidden subgraphs
• Highly linked graphs
• Trennende Knotenpunktmengen und Reduzibilität abstrakter Graphen mit Anwendung auf das Vierfarbenproblem.
• On Sufficient Degree Conditions for a Graph to be $k$-linked
• On the structure of 5- and 6-chromatic abstract graphs.
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs