Randomly coloring graphs with lower bounds on girth and maximum degree

DOI10.1002/rsa.10087zbMath1028.05030OpenAlexW2075846823WikidataQ56323969 ScholiaQ56323969MaRDI QIDQ4434470

Martin Dyer, Alan M. Frieze

Publication date: 10 November 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10087

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Related Items (13)

Randomly coloring planar graphs with fewer colors than the maximum degree ⋮ Coupling with the stationary distribution and improved sampling for colorings and independent sets ⋮ Phase transition for the mixing time of the Glauber dynamics for coloring regular trees ⋮ Perfect sampling from spatial mixing ⋮ Complexity results for MCMC derived from quantitative bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Mixing time of exponential random graphs ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Randomly coloring random graphs ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ Local uniformity properties for glauber dynamics on graph colorings ⋮ Randomly coloring constant degree graphs

Cites Work

• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• Unnamed Item

This page was built for publication: Randomly coloring graphs with lower bounds on girth and maximum degree