Choosability with separation in graphs and hypergraphs

Mohit Kumbhat

Department of Mathematics, Sungkyunkwan University, Suwon, South Korea

Department of Mathematics, Sungkyunkwan University, Suwon, South Korea

2012/11/22

*Thu*4PM-5PMFor a hypergraph G and a positive integer c, let χ

_{ℓ}(G,c) be the minimum value of ℓ such that G is L-colorable from every list L with |L(v)|=ℓ for each v∈V(G) and |L(u)∩L(v)|≤c for all e=uv∈E(G). This parameter was studied by Kratochvíl, Tuza and Voigt for various kinds of graphs. In this talk, we present the asymptotics of χ_{ℓ}(G,c) for complete graphs, complete multipartite graphs and hypergraphs. This is a joint work with Z. Füredi and A. Kostochka.