Coloring graphs of various maximum degree from random lists. Issue 1 (20th August 2017)

• Record Type: Journal Article
• Authors: Casselgren, Carl Johan
• Is Part Of: Random structures & algorithms. Volume 52:Issue 1(2018)
• Page Start: 54
• Page End: 73
• Publication Date: 2017-08-20
• Subjects: coloring from random lists -- list coloring -- random list; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20725
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Let G = G ( n ) be a graph on n vertices with maximum degree Δ =Δ ( n ). Assign to each vertex v of G a list L ( v ) of colors by choosing each list independently and uniformly at random from all k ‐subsets of a color set C of size C σ = σ ( n ) . Such a list assignment is called a random ( k, C ) ‐list assignment . In this paper, we are interested in determining the asymptotic probability (as n → ∞ ) of the existence of a proper coloring φ of G, such that φ ( v ) ∈ L ( v ) for every vertex v of G, a so‐called L ‐coloring. We give various lower bounds on σ, in terms of n, k, and Δ, which ensures that with probability tending to 1 as n → ∞ there is an L ‐coloring of G . In particular, we show, for all fixed k and growing n, that if σ ( n ) = ω ( n 1 / k 2 Δ 1 / k ) and Δ = O ( n k − 1 k ( k 3 + 2 k 2 − k + 1 ) ), then the probability that G has an L ‐coloring tends to 1 as n → ∞ . If k ≥ 2 and Δ = Ω ( n 1 / 2 ), then the same conclusion holds provided that σ = ω ( Δ ) . We also give related results for other bounds on Δ, when k is constant or a strictly increasing function of n .