Refined list version of Hadwiger’ conjecture
Yangyan Gu
Charles University and Zhejiang Normal University
March 9, 2023, 12:20 in S6
Abstract
The concept of \lambda-choosability is a refinement of choosability that puts k-choosability and k-colourability in the same framework. If |\lambda| is close to k_\lambda, then \lambda-choosability is close to k_\lambda-colourability; if |\lambda| is close to 1, then \lambda-choosability is close to k_\lambda-choosability. We study Hadwiger's Conjecture in the context of such a refined list colouring. Hadwiger's Conjecture is equivalent to saying that every K_t-minor-free graph is {1 \star (t-1)}-choosable for any positive integer t. We prove that for t >= 5, for any partition \lambda of t-1 other than {1 \star (t-1)}, there is a K_t-minor-free graph G that is not \lambda-choosable. We then construct several types of K_t-minor-free graphs that are not \lambda-choosable, where k_\lambda-(t-1) gets larger as k_\lambda-|\lambda| gets larger.