On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture (Q858685)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture |
scientific article; zbMATH DE number 5115323
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture |
scientific article; zbMATH DE number 5115323 |
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
0.8973853
0 references
0.8921646
0 references
0 references
0.87373555
0 references
0 references
0.87345994
0 references
0.8720229
0 references
0.8719372
0 references
0.87125057
0 references
0 references
