OAI.LinearListHadwiger.main_theorem

The theorem states that there is a natural number C ≥ 1 such that, for every finite nonempty vertex type V and every simple graph G on V, the list chromatic number of G is at most C times the Hadwiger number of G. A graph is list colorable from an assignment L of finite color sets to vertices if one can pick, for every vertex v, a color c(v) in L(v) so that adjacent vertices receive different colors. G is k-choosable if, for every color type and every assignment L with each |L(v)| ≥ k, G is list colorable from L, and the list chromatic number is the infimum of the k for which G is k-choosable. G has a clique minor of order t if there are t pairwise disjoint vertex sets B(0),…,B(t−1), each inducing a connected subgraph of G, such that any two distinct sets contain adjacent vertices (one in each). The Hadwiger number is the supremum of the t for which G has a clique minor of order t. The bound C is a single constant independent of V and G.