On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.36OpenAlexW2978040167MaRDI QIDQ5875492

Michael Anastos, Alan M. Frieze

Publication date: 3 February 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11251/pdf/LIPIcs-APPROX-RANDOM-2019-36.pdf

zbMATH Keywords

ergodicityrandom graphscolorings

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Fast recoloring of sparse graphs
• Paths between colourings of sparse graphs
• Constraining the clustering transition for colorings of sparse random graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• Phase transitions in theq-coloring of random hypergraphs
• Sampling Random Colorings of Sparse Random Graphs
• Hypergraph coloring up to condensation
• Rigid Colorings of Hypergraphs and Contiguity
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The freezing threshold for k-colourings of a random graph
• On the solution‐space geometry of random constraint satisfaction problems
• The condensation phase transition in random graph coloring

This page was built for publication: On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs