A relaxed Hadwiger's conjecture for list colorings (Q885300)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A relaxed Hadwiger's conjecture for list colorings |
scientific article |
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