An improved upper bound on the non-3-colourability threshold
From MaRDI portal
Publication:293171
DOI10.1016/S0020-0190(97)00193-2zbMath1339.05128MaRDI QIDQ293171
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
Related Items
Upper-bounding the \(k\)-colorability threshold by counting covers, Small maximal matchings in random graphs.
Cites Work
- Unnamed Item
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- The hardest constraint problems: A double phase transition
- Many hard examples for resolution
- Approximating the unsatisfiability threshold of random formulas
- A threshold for unsatisfiability