Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On randomly colourin ...
Article

On randomly colouring locally sparse graphs

Alan Frieze ORCID (1), Juan Vera (1)
(1) Department of Mathematical Sciences [Pittsburgh]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2006
Last modified on
March 31, 2025
Volume 8
vol. 8
DOI
10.46298/dmtcs.360
License
https://about.hal.science/hal-authorisation-v1
National Science Foundation
0200945
Probabilistic Considerations in the Analysis of Algorithms
Indicators
925
Views
1050
Downloads

On randomly colouring locally sparse graphs

Alan Frieze ORCID (1), Juan Vera (1)
(1) Department of Mathematical Sciences [Pittsburgh]
Abstract
We consider the problem of generating a random q-colouring of a graph G=(V,E). We consider the simple Glauber Dynamics chain. We show that if for all v ∈ V the average degree of the subgraph H_v induced by the neighbours of v ∈ V is #x226a Δ where Δ is the maximum degree and Δ >c_1\ln n then for sufficiently large c_1, this chain mixes rapidly provided q/Δ >α , where α #x2248 1.763 is the root of α = e^\1/α \. For this class of graphs, which includes planar graphs, triangle free graphs and random graphs G_\n,p\ with p #x226a 1, this beats the 11Δ /6 bound of Vigoda for general graphs.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Counting Colourings
  • Sampling
  • Markov Chains
Cited by

Source: OpenCitations

  • A class of stochastic games with infinitely many interacting agents related to Glauber dynamics on random graphs

    Dipòsit Digital de Documents de la UAB (Universitat Autònoma de Barcelona)

    Authors : Emilio De Santis ORCID, Carlo Marinelli ORCID

    Journal reference : Volume 40, 2007, pp. 11777-11790

    DOI : 10.1088/1751-8113/40/39/006

  • A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings

    2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

    Authors : Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan ORCID

    Journal reference : Volume 116, 2022, pp. 161-172

    DOI : 10.1109/focs52979.2021.00024

  • Bounds for the Independence and Chromatic Numbers of Locally Sparse Graphs

    Annals of Combinatorics

    Authors : Abhishek Dhawan ORCID

    Journal reference : Volume 30, 2025, pp. 277-304

    DOI : 10.1007/s00026-025-00778-7

  • A Deterministic Algorithm for Counting Colorings with 2-Delta Colors

    arXiv (Cornell University)

    Authors : Jingcheng Liu ORCID, Alistair Sinclair ORCID, Piyush Srivastava ORCID

    Journal reference : Volume , 2019, pp. 1380-1404

    DOI : 10.1109/focs.2019.00085

  • Randomly coloring planar graphs with fewer colors than the maximum degree

    Random Structures and Algorithms

    Authors : Thomas P. Hayes ORCID, Juan C. Vera ORCID, Eric Vigoda

    Journal reference : Volume 47, 2014, pp. 731-759

    DOI : 10.1002/rsa.20560

  • A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold

    SIAM Journal on Computing

    Authors : Charilaos Efthymiou

    Journal reference : Volume 45, 2016, pp. 2087-2116

    DOI : 10.1137/140977643

  • Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions

    arXiv (Cornell University)

    Authors : Jingcheng Liu ORCID, Alistair Sinclair ORCID, Piyush Srivastava ORCID

    Journal reference : Volume 54, 2022, pp. FOCS19-200

    DOI : 10.1137/20m1317384
Preview
Loading PDF preview...