Premium
Coloring graphs from random lists of fixed size
Author(s) -
Casselgren Carl Johan
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20469
Subject(s) - combinatorics , mathematics , vertex (graph theory) , random graph , complete coloring , bounded function , list coloring , fractional coloring , discrete mathematics , graph , random regular graph , greedy coloring , struct , chordal graph , graph power , computer science , 1 planar graph , line graph , mathematical analysis , programming language
Let G = G ( n ) be a graph on n vertices with maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L ( v ) of colors by choosing each list uniformly at random from all k ‐subsets of a color set C of size σ ( 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 . We show, for all fixed k and growing n , that if σ ( n ) = ω ( n 1 / k 2) , then the probability that G has such a proper coloring tends to 1 as n → ∞ . A similar result for complete graphs is also obtained: if σ ( n ) ≥ 1.223 n and L is a random ( 3 , C ) ‐list assignment for the complete graph K n on n vertices, then the probability that K n has a proper coloring with colors from the random lists tends to 1 as n → ∞ .Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 317‐327, 2014