A note on the non-colorability threshold of a random graph

zbMath0939.05073MaRDI QIDQ1978060

Lefteris M. Kirousis, Yannis C. Stamatiou, Alexis C. Kaporis

Publication date: 7 June 2000

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/120357

zbMATH Keywords

random graphscoloringsoccupancy problemnon-colorability

Mathematics Subject Classification ID

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

Related Items (4)

Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Almost all graphs with average degree 4 are 3-colorable ⋮ When does the giant component bring unsatisfiability? ⋮ A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs

This page was built for publication: A note on the non-colorability threshold of a random graph