Randomly coloring sparse random graphs with fewer colors than the maximum degree
From MaRDI portal
Publication:3419603
DOI10.1002/rsa.20129zbMath1115.05030OpenAlexW4242643895WikidataQ56323897 ScholiaQ56323897MaRDI QIDQ3419603
Eric Vigoda, Abraham D. Flaxman, Martin Dyer, Alan M. Frieze
Publication date: 7 February 2007
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20129
Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Coloring of graphs and hypergraphs (05C15)
Related Items
Recoloring Planar Graphs of Girth at Least Five, Classifying coloring graphs, A Spectral Independence View on Hard Spheres via Block Dynamics, A polynomial version of Cereceda's conjecture, Parameterized complexity of the list coloring reconfiguration problem with graph parameters, Randomly coloring planar graphs with fewer colors than the maximum degree, Random Instances of Problems in NP – Algorithms and Statistical Physics, Unnamed Item, On Sampling Simple Paths in Planar Graphs According to Their Lengths, Forbidden subgraphs of coloring graphs, Reconfiguration in bounded bandwidth and tree-depth, Finding Paths between Graph Colourings: Computational Complexity and Possible Distances, Fast recoloring of sparse graphs, Block symmetries in graph coloring reconfiguration systems, Digraph redicolouring, Reconfiguration graphs of zero forcing sets, Unnamed Item, On the connectivity of proper colorings of random graphs and hypergraphs, An update on reconfiguring 10-colorings of planar graphs, Cut-colorings in coloring graphs, Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs, Recoloring graphs of treewidth 2, Connectedness of the graph of vertex-colourings, Random sampling of colourings of sparse random graphs with a constant number of colours, Constraining the clustering transition for colorings of sparse random graphs, Unnamed Item, Mixing time of an unaligned Gibbs sampler on the square, Rapid mixing of Gibbs sampling on graphs that are sparse on average, Randomly coloring random graphs, The mixing time of Glauber dynamics for coloring regular trees, Local convergence of random graph colorings, Gibbs rapidly samples colorings of \(G(n, d/n)\), Reconfiguring vertex colourings of 2-trees, The Glauber dynamics for edge‐colorings of trees, A Reconfigurations Analogue of Brooks' Theorem and Its Consequences, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Approximate Counting via Correlation Decay in Spin Systems, Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters, Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs, Introduction to reconfiguration, A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold, Unnamed Item
Cites Work
