Randomly coloring graphs of girth at least five

DOI10.1145/780542.780584zbMath1192.05050OpenAlexW2030932831MaRDI QIDQ3581296

Thomas P. Hayes

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780584

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Coupling with the stationary distribution and improved sampling for colorings and independent sets ⋮ Adaptable and conflict colouring multigraphs with no cycles of length three or four ⋮ Unnamed Item ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Glauber dynamics on trees: Boundary conditions and mixing time ⋮ Fast mixing for independent sets, colorings, and other models on trees ⋮ Variable length path coupling ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ Randomly coloring sparse random graphs with fewer colors than the maximum degree

This page was built for publication: Randomly coloring graphs of girth at least five