A relaxed Hadwiger's conjecture for list colorings (Q885300)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5162683
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A relaxed Hadwiger's conjecture for list colorings |
scientific article; zbMATH DE number 5162683 |
Statements
A relaxed Hadwiger's conjecture for list colorings (English)
0 references
8 June 2007
0 references
The authors prove the following result: For every positive integer \(k\), there exists a computable constant \(f(k)\) such that every finite and simple graph \(G\) without \(K_k\) as a minor admits a vertex partition \(V_1,\dots, V_{\lceil 15.5k\rceil}\) such that every component in the subgraph of \(G\) induced on \(V_i\) has at most \(f(k)\) vertices. This result is extended to list colorings and a conjecture is posed, too.
0 references
Hadwiger's conjecture
0 references
list coloring
0 references
0.8450961112976074
0 references
0.8305473923683167
0 references
0.8233339190483093
0 references
0.815778911113739
0 references
0.8142578601837158
0 references