An improved upper bound on the non-3-colourability threshold

DOI10.1016/S0020-0190(97)00193-2MaRDI QIDQ293171zbMATH OpenOpenAlexFDO

Authors Paul E. Dunne, Michele Zito

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097001932?np=y

zbMATH Keywords

3-colouringphase transition threshold

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1919507
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• A note on the non-colorability threshold of a random graph
• Almost all graphs with average degree 4 are 3-colorable
• Upper-bounding the k-colorability threshold by counting covers

Cites work

• A threshold for unsatisfiability
• Approximating the unsatisfiability threshold of random formulas
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• scientific article; zbMATH DE number 1114008 (Why is no real title available?)
• Many hard examples for resolution
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• The hardest constraint problems: A double phase transition

Cited in

(5)

• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• Small maximal matchings in random graphs.
• A note on the non-colorability threshold of a random graph
• Upper-bounding the k-colorability threshold by counting covers
• scientific article; zbMATH DE number 1919507 (Why is no real title available?)

This page was built for publication: An improved upper bound on the non-3-colourability threshold

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