A relaxed Hadwiger's Conjecture for list colorings

Hadwiger's Conjecture claims that any graph without Kk as a minor is (k−1)-colorable. It has been proved for k⩽6, and is still open for every k⩾7. It is not even known if there exists an absolute constant c such that any ck-chromatic graph has Kk as a minor. Motivated by this problem, we show that there exists a computable constant f(k) such that any graph G without Kk as a minor admits a vertex partition V1,…,V⌈15.5k⌉ such that each component in the subgraph induced on Vi (i⩾1) has at most f(k) vertices. This result is also extended to list colorings for which we allow monochromatic components of order at most f(k). When f(k)=1, this is a coloring of G. Hence this is a relaxation of coloring and this is the first result in this direction.