KAIST Discrete Math Seminar

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