Alan Frieze ; Juan Vera - On randomly colouring locally sparse graphs

dmtcs:360 - Discrete Mathematics & Theoretical Computer Science, January 1, 2006, Vol. 8 - https://doi.org/10.46298/dmtcs.360
On randomly colouring locally sparse graphs

Authors: Alan Frieze ORCID-iD; Juan Vera

    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.


    Volume: Vol. 8
    Published on: January 1, 2006
    Imported on: March 26, 2015
    Keywords: Counting Colourings,Sampling,Markov Chains,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Fundings :
      Source : OpenAIRE Research Graph
    • Probabilistic Considerations in the Analysis of Algorithms; Funder: National Science Foundation; Code: 0200945

    3 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 169 times.
    This article's PDF has been downloaded 270 times.