Title: A small step forward in bipartite list coloring.
Abstract: The choosability of a graph G is the minimum value k such that G has a proper list coloring whenever each vertex of G has a list of k colors. Molloy showed that if G is a triangle-free graph of maximum degree d, then the choosability of G is at most (1 + o(1)) d / log d and that this bound is tight within a factor of roughly 2. It is widely believed that this upper bound can be greatly improved in the special case that G is bipartite, and Alon and Krivelevich conjectured an upper bound of O(log d) in this case. However, little progress has been made toward solving this conjecture, and it is currently unknown whether the optimal upper bound for bipartite graphs is different from the optimal upper bound for triangle-free graphs.
In this talk, we use a modification of a probabilistic coupon-collector argument from Alon, Cambie, and Kang to show that every bipartite graph of maximum degree d has choosability at most 0.797 d / log d. Our result provides evidence that the list-coloring problem is fundamentally easier in bipartite graphs than in triangle-free graphs. It hence takes a small but important step toward solving the conjecture of Alon and Krivelevich. (The content of this talk is part of ongoing work with Bojan Mohar and Ladislav Stacho.)