A relaxed Hadwiger's conjecture for list colorings (Q885300): Difference between revisions

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.