Premium
Strong spatial mixing of list coloring of graphs
Author(s) -
Gamarnik David,
Katz Dmitriy,
Misra Sidhant
Publication year - 2015
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.20518
Subject(s) - mathematics , combinatorics , bounded function , degree (music) , uniqueness , brooks' theorem , vertex (graph theory) , mixing (physics) , list coloring , fractional coloring , discrete mathematics , graph coloring , constant (computer programming) , graph , 1 planar graph , chordal graph , computer science , graph power , line graph , physics , mathematical analysis , quantum mechanics , acoustics , programming language
The property of spatial mixing and strong spatial mixing in spin systems has been of interest because of its implications on uniqueness of Gibbs measures on infinite graphs and efficient approximation of counting problems that are otherwise known to be # P hard. In the context of coloring, strong spatial mixing has been established for Kelly trees in (Ge and Stefankovic, arXiv:1102.2886v3 (2011)) when q ≥ α * Δ + 1 where q the number of colors, Δ is the degree andα * = 1.763 .. is the unique solution to x e − 1 / x = 1 . It has also been established in (Goldberg et al., SICOMP 35 (2005) 486–517) for bounded degree lattice graphs whenever q ≥ α * Δ − β for some constant β, where Δ is the maximum vertex degree of the graph. We establish strong spatial mixing for a more general problem, namely list coloring, for arbitrary bounded degree triangle‐free graphs. Our results hold for any α > α * whenever the size of the list of each vertex v is at least α Δ ( v ) + β where Δ ( v ) is the degree of vertex v and β is a constant that only depends on α. The result is obtained by proving the decay of correlations of marginal probabilities associated with graph nodes measured using a suitably chosen error function. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,599–613, 2015