On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture (Q858685)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture |
scientific article |
Statements
On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture (English)
0 references
11 January 2007
0 references
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.
0 references
contraction-critical graphs
0 references
0 references