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. ----------------------------------------------------