Randomly coloring graphs of girth at least five

DOI10.1145/780542.780584MaRDI QIDQ3581296zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Randomly Colouring Graphs with Girth Five and Large Maximum Degree
• Randomly coloring constant degree graphs
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• Randomly coloring graphs with lower bounds on girth and maximum degree

Cited in

(16)

• Glauber dynamics on trees: Boundary conditions and mixing time
• Randomly coloring constant degree graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Randomly Colouring Graphs with Girth Five and Large Maximum Degree
• Randomly coloring graphs with lower bounds on girth and maximum degree
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• Sampling random colorings of sparse random graphs
• Randomly coloring graphs of logarithmically bounded pathwidth
• Fast mixing for independent sets, colorings, and other models on trees
• Variable length path coupling
• Approximate counting via correlation decay in spin systems
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Adaptable and conflict colouring multigraphs with no cycles of length three or four
• Deterministic approximate counting of colorings with fewer than 2 colors via absence of zeros
• Correlation decay and partition function zeros: algorithms and phase transitions
• Coupling with the stationary distribution and improved sampling for colorings and independent sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581296)