Choosability with separation of complete multipartite graphs and hypergraphs

2011/09/14 by Zoltán Füredi, Füredi, Zoltán, Alexandr Kostochka +3 · 2 citations
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.1109.2969

9 pages

arxiv created 2011/09/14 · arxiv updated 2011/09/15

Abstract

For a hypergraph G and a positive integer s, let χ_ℓ (G,s) be the minimum value of l such that G is L-colorable from every list L with |L(v)|=l for each v∈ V(G) and |L(u)∩ L(v)|≤ s for all u, v∈ e∈ E(G). This parameter was studied by Kratochvíl, Tuza and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of χ_ℓ (G,s) for balanced complete multipartite graphs and for complete k-partite k-uniform hypergraphs.

Cited by

• Single conflict coloring, adaptable choosability and separation choosability
• Choosability with Separation in Complete Multipartite Graphs

Related

• Choosability of multipartite hypergraphs
• Choosability with Separation in Complete Multipartite Graphs
• Choosability with Separation of Cycles and Outerplanar Graphs
• A Note on the Equitable Choosability of Complete Bipartite Graphs
• Bipartite graphs are ((4)/(5)-ε) \fracΔlog Δ-choosable