A reminder: this is today.
------------------------------------------------------
On 2023-03-06 09:11, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 9 March, given by Yangyan Gu. Please find the talk details below.
Best regards, Misha Tyomkyn.
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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz