Article

Randomly coloring graphs of girth at least five

Author:

Thomas P. HayesAuthors Info & Claims

STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

Pages 269 - 278

https://doi.org/10.1145/780542.780584

Published: 09 June 2003 Publication History

Get Access

Abstract

We improve rapid mixing results for the simple Glauber dynamics designed to generate a random k-coloring of a bounded-degree graph.Let G be a graph with maximum degree Δ = Ω(log n), and girth ≥ 5. We prove that if k > Α Δ, where Α ≈ 1.763 then Glauber dynamics has mixing time O(n log n). If girth(G) ≥ 6 and k > Β Δ, where Β ≈ 1.489 then Glauber dynamics has mixing time O(n log n). This improves a recent result of Molloy, who proved the same conclusion under the stronger assumptions that Δ=Ω(log n) and girth Ω(log Δ). Our work suggests that rapid mixing results for high girth and degree graphs may extend to general graphs.Analogous results hold for random graphs of average degree up to n^¼, compared with polylog(n), which was the best previously known.Some of our proofs rely on a new Chernoff-Hoeffding type bound, which only requires the random variables to be well-behaved with high probability. This tail inequality may be of independent interest.

References

[1]

G. Brightwell and P. Winkler. Random colorings of a Cayley tree. In B. Bollobas, editor, Contemporary Combinatorics, volume 10 of Bolyai Society Mathematical Studies. Springer Verlag, 2002.

Google Scholar

[2]

R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 223--231. IEEE, October 1997.

Digital Library

Google Scholar

[3]

D. Dubhashi. Simple proofs of occupancy tail bounds. Random Structures and Algorithms, 11(2):119--123, 1997.

Digital Library

Google Scholar

[4]

D. Dubhashi and D. Ranjan. Balls and bins: a study in negative dependence. Random Structures and Algorithms, 13(2):99--124, 1998.

Digital Library

Google Scholar

[5]

M. Dyer and A. Frieze. Randomly colouring graphs with lower bounds on girth and maximum degree. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pages 579--587. IEEE, October 2001.

Digital Library

Google Scholar

[6]

M. Dyer, C. Greenhill, and M. Molloy. Very rapid mixing of the Glauber dynamics for proper colourings on bounded-degree graphs. Random Structures and Algorithms, 20:98--114, 2002.

Digital Library

Google Scholar

[7]

T. Hayes. Randomly coloring bipartite graphs. Manuscript, in progress, 2003.

Google Scholar

[8]

T. Hayes and E. Vigoda. A non-Markovian coupling technique. Technical Report TR-2003-02, University of Chicago, February 2003.

Google Scholar

[9]

M. Jerrum. A very simple algorithm for estimating the number of k-colourings of a low-degree graph. Random Structures and Algorithms, 7:157--165, 1995.

Crossref

Google Scholar

[10]

M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169--188, 1986.

Crossref

Google Scholar

[11]

M. Molloy. The Glauber dynamics on colorings of a graph with high girth and maximum degree. In Proceedings of the 34th Annual ACM Symposium on Theory of Computer Science, pages 91--98, 2002.

Digital Library

Google Scholar

[12]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.

Digital Library

Google Scholar

[13]

J. Salas and A. Sokal. Absence of phase transition for anti-ferromagnetic Potts models via the Dobrushin uniqueness theorem. Journal of Statistical Physics, 86:551--579, 1997.

Crossref

Google Scholar

[14]

E. Vigoda. Improved bounds for sampling colorings. J. Math. Phys., 41:155--169, 2000.

Crossref

Google Scholar

Cited By

View all

Aliaj JMolloy M(2023)Adaptable and conflict colouring multigraphs with no cycles of length three or fourJournal of Graph Theory10.1002/jgt.22956104:1(188-219)Online publication date: 10-Apr-2023
https://doi.org/10.1002/jgt.22956
Feng WGuo HYin YZhang C(2022)Rapid Mixing from Spectral Independence beyond the Boolean DomainACM Transactions on Algorithms10.1145/353100818:3(1-32)Online publication date: 11-Oct-2022
https://dl.acm.org/doi/10.1145/3531008
Liu JSinclair ASrivastava P(2022)Correlation Decay and Partition Function Zeros: Algorithms and Phase TransitionsSIAM Journal on Computing10.1137/20M1317384(FOCS19-200-FOCS19-252)Online publication date: 26-Jul-2022
https://doi.org/10.1137/20M1317384
Show More Cited By

Index Terms

Randomly coloring graphs of girth at least five
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
  2. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

b-coloring of tight graphs

A coloring c of a graph G=(V,E) is a b-coloring if in every color class there is a vertex whose neighborhood intersects every other color class. The b-chromatic number of G, denoted @g"b(G), is the greatest integer k such that G admits a b-coloring with ...
An oriented coloring of planar graphs with girth at least five

An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented graph with a maximum average degree less than 103 and girth at least 5 has an oriented chromatic number at most 16. ...
L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs

The frequency assignment problem is to assign a frequency to each radio transmitter so that transmitters are assigned frequencies with allowed separations. Motivated by a variation of the frequency assignment problem, the L(2,1)-labeling problem was put ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

June 2003

740 pages

ISBN:1581136749

DOI:10.1145/780542

Conference Chair:
Lawrence L. Larmore
University of Nevada Las Vegas, Las Vegas, NV
,
Program Chair:
Michel X. Goemans
Massachusetts Institute of Technology, Cambridge, MA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC03

Sponsor:

STOC03: The 35th Annual ACM Symposium on Theory of Computing

June 9 - 11, 2003

CA, San Diego, USA

Acceptance Rates

STOC '03 Paper Acceptance Rate 80 of 270 submissions, 30%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
429
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Aliaj JMolloy M(2023)Adaptable and conflict colouring multigraphs with no cycles of length three or fourJournal of Graph Theory10.1002/jgt.22956104:1(188-219)Online publication date: 10-Apr-2023
https://doi.org/10.1002/jgt.22956
Feng WGuo HYin YZhang C(2022)Rapid Mixing from Spectral Independence beyond the Boolean DomainACM Transactions on Algorithms10.1145/353100818:3(1-32)Online publication date: 11-Oct-2022
https://dl.acm.org/doi/10.1145/3531008
Liu JSinclair ASrivastava P(2022)Correlation Decay and Partition Function Zeros: Algorithms and Phase TransitionsSIAM Journal on Computing10.1137/20M1317384(FOCS19-200-FOCS19-252)Online publication date: 26-Jul-2022
https://doi.org/10.1137/20M1317384
Feng WGuo HYin YZhang CMarx D(2021)Rapid mixing from spectral independence beyond the boolean domainProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458159(1558-1577)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458159
Chen SDelcourt MMoitra APerarnau GPostle LChan T(2019)Improved bounds for randomly sampling colorings via linear programmingProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310569(2216-2234)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310569
Lu PYang KZhang CZhu MKlein P(2017)An FPTAS for counting proper four-colorings on cubic graphsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039803(1798-1817)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039803
Conte AKurita KWasa KUno T(2017)Listing Acyclic Subgraphs and Subgraphs of Bounded Girth in Directed GraphsCombinatorial Optimization and Applications10.1007/978-3-319-71147-8_12(169-181)Online publication date: 16-Nov-2017
https://doi.org/10.1007/978-3-319-71147-8_12
Lu PYin Y(2013)Improved FPTAS for Multi-spin SystemsApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-40328-6_44(639-654)Online publication date: 2013
https://doi.org/10.1007/978-3-642-40328-6_44
Li LLu PYin Y(2012)Approximate counting via correlation decay in spin systemsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095190(922-940)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095190
Kuo CLu H(2012)Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common NeighborsAlgorithms and Computation10.1007/978-3-642-35261-4_6(24-33)Online publication date: 2012
https://doi.org/10.1007/978-3-642-35261-4_6
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

b-coloring of tight graphs

An oriented coloring of planar graphs with girth at least five

L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs