On the connectivity of proper colorings of random graphs and hypergraphs

DOI10.1002/rsa.20912zbMath1452.05167OpenAlexW3005287390MaRDI QIDQ5128749

Michael Anastos, Alan M. Frieze

Publication date: 26 October 2020

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20912

zbMATH Keywords

connectivity of coloringsrandom hypergraph coloring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• On colouring random graphs
• Cliques in random graphs
• The Freezing Threshold for k -Colourings of a Random Graph
• Phase transitions in theq-coloring of random hypergraphs
• Rigid Colorings of Hypergraphs and Contiguity
• Planting Colourings Silently
• Gibbs states and the set of solutions of random constraint satisfaction problems
• On the solution‐space geometry of random constraint satisfaction problems
• The condensation phase transition in random graph coloring