On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
type: Item
instance of: scholarly article
title: On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
zbMATH Open document ID: 1107.05034
published in: Journal of Combinatorial Theory. Series B
publication date: 2007-01-11T00:00:00Z
review text: The Hadwiger conjecture states that every \(k\)-chromatic graph has a \(K_{k}\)-minor. The author proves that for all positive integers \(k\), any minimal \(k\)-chromatic counterexample to Hadwiger's conjecture is \(\lceil 2k/27 \rceil\)-connected. This is the first result on the vertex connectivity of a minimal counterexample to Hadwiger's conjecture.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 5115323
zbMATH Keywords: contraction-critical graphs
author: Ken-ichi Kawarabayashi
MaRDI profile type: Publication
full work available at URL: j.jctb.2006.04.004
OpenAlex ID: W2135517930
cites work: Every planar map is four colorable. I: Discharging
cites work: Every planar map is four colorable. II: Reducibility
cites work: Linear connectivity forces large complete bipartite minors
cites work: Highly linked graphs
cites work: Graphs with forbidden subgraphs
cites work: Q4342632
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Trennende Knotenpunktmengen und Reduzibilität abstrakter Graphen mit Anwendung auf das Vierfarbenproblem.
cites work: On the structure of 5- and 6-chromatic abstract graphs.
cites work: Vertex-disjoint cycles containing specified edges
cites work: Q5837979
cites work: Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
cites work: Non-zero disjoint cycles in highly connected group labelled graphs
cites work: On Sufficient Degree Conditions for a Graph to be $k$-linked
cites work: Über trennende Eckenmengen in homomorphiekritischen Graphen
cites work: Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. XX: Wagner's conjecture
cites work: Hadwiger's conjecture for \(K_ 6\)-free graphs
cites work: The four-colour theorem
cites work: An improved linear edge bound for graph linkages
cites work: On separating sets of edges in contraction-critical graphs
cites work: Q3035307
DOI: 10.1016/J.JCTB.2006.04.004
Recommended article: Connectivities for \(k\)-knitted graphs and for minimal counterexamples to Hadwiger's conjecture
Recommended article: Minimal counterexamples to a conjecture of Hall and Paige
Recommended article: On minimally \(k\)-connected matroids
Recommended article: A general minimax theorem based on connectedness
Recommended article: On minor-minimally-connected matroids
Recommended article: Highly connected counterexamples to a conjecture on α -domination
Recommended article: A counterexample to a conjecture on the connectivity of \(0\)-\(1\) polytope graphs
Recommended article: On minimally \((n,\lambda)\)-connected graphs
Recommended article: Connected matchings and Hadwiger's conjecture
Recommended article: Über ein Gegenbeispiel zur Hirsch-Vermutung
description: scientific article; zbMATH DE number 5115323