Almost all graphs with average degree 4 are 3-colorable
Authors:
- Dimitris AchlioptasDADimitris Achlioptas
- Cristopher MooreCMCristopher Moore
- 1 September 2003
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 67 (2) , 441-471
Abstract
No abstract availableKeywords
This publication has 19 references indexed in Scilit:
- The analysis of a list-coloring algorithm on a random graph2002
- Optimization with Extremal DynamicsPhysical Review Letters, 2001
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)2000
- A Note on the Non-Colorability Threshold of a Random GraphThe Electronic Journal of Combinatorics, 2000
- A Sharp Threshold fork-ColorabilityRandom Structures & Algorithms, 1999
- Almost all graphs with 1.44n edges are 3‐colorableRandom Structures & Algorithms, 1991
- Stable husbandsRandom Structures & Algorithms, 1990
- Maximum matching in sparse random graphs1981
- New methods to color the vertices of a graphCommunications of the ACM, 1979
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978