The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree

DOI10.1137/S0097539702401786zbMath1105.68116OpenAlexW1981764507MaRDI QIDQ4651490

No author found.

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539702401786

zbMATH Keywords

Glauber dynamicscoloringsrapidly mixing Markov chains

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Related Items (18)

Classifying coloring graphs ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Coupling with the stationary distribution and improved sampling for colorings and independent sets ⋮ Forbidden subgraphs of coloring graphs ⋮ Perfect sampling from spatial mixing ⋮ Block symmetries in graph coloring reconfiguration systems ⋮ Reconfiguration graphs of zero forcing sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cut-colorings in coloring graphs ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Random sampling of colourings of sparse random graphs with a constant number of colours ⋮ Randomly coloring random graphs ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ Reconfiguration graphs for dominating sets ⋮ Local uniformity properties for glauber dynamics on graph colorings ⋮ Randomly coloring constant degree graphs ⋮ Strong spatial mixing of list coloring of graphs

This page was built for publication: The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree