On the connectivity of proper colorings of random graphs and hypergraphs

DOI10.1002/RSA.20912MaRDI QIDQ5128749zbMATH OpenOpenAlexFDO

Authors Michael Anastos, Alan 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

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

Recommendations

• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
• On the chromatic index of random uniform hypergraphs
• Randomly coloring simple hypergraphs with fewer colors
• Randomly coloring simple hypergraphs
• Two‐coloring random hypergraphs

Cites work

• Cliques in random graphs
• Constraining the clustering transition for colorings of sparse random graphs
• Fast recoloring of sparse graphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• On colouring random graphs
• On the solution-space geometry of random constraint satisfaction problems
• Paths between colourings of sparse graphs
• Phase transitions in the \(q\)-coloring of random hypergraphs
• Planting colourings silently
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Rigid colorings of hypergraphs and contiguity
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• The condensation phase transition in random graph coloring
• The freezing threshold for \(k\)-colourings of a random graph

Cited in

(4)

• Randomly coloring simple hypergraphs
• On the strength of connectedness of a random hypergraph
• Randomly coloring simple hypergraphs with fewer colors
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs

This page was built for publication: On the connectivity of proper colorings of random graphs and hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128749)