On 13 March 2023 09:29:29 CET, Mykhaylo Tyomkyn <tyomkyn@kam.mff.cuni.cz> wrote:

Dear all,

There will be a noon seminar this Thursday, 16 March, given by Jailu Zhu.
Please find the talk details below.

Best regards,
Misha Tyomkyn.
The generalization of Ohba conjecture
Jailu Zhu
Charles University and Zhejiang Normal University
March 16, 2023, 12:20 in S6

Abstract
It is well-known that there is a big gap between k-colourability and k-choosability. In particular, bipartite graphs can have arbitrary large choice number. An interesting problem is for which graphs G, chromatic number equals to choice number. Such graphs are called chromatic-choosable. There are a few challenging conjectures that assert certain families of graphs are chromatic-choosable. The most famous problem concerning this concept is perhaps the list coloring conjecture, which asserts that line graphs are chromatic-choosable. Another problem concerning chromatic-choosable graphs is the minimum order of a non-chromatic-choosable graph with given chromatic number.

For a positive integer k, let f(k) be the minimum n such that there is a non k-choosable k-chromatic n-vertex graph. Ohba conjectured that f(k) is at least 2k+2 and this conjecture was finally confirmed by Noel, Reed and Wu in 2014. Intuitively, the reason that a k-colourable graph fails to be L-colourable for a k-list assignment L is due to the fact that lists assigned to vertices by L may be complicately entangled. In 2019, Xuding Zhu put restrictions on the entanglements of lists that are allowed to be assigned to the vertices, and hence builds a refined scale for measuring choosability of graphs.

Now, we consider the similar Ohba problem under that refined scale. For a multi set lambda of k_lambda, we define f(lambda) similarly and we can determine the value of f(lambda) for all lambda.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz
To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz