Almost all graphs with average degree 4 are 3-colorable

DOI10.1016/S0022-0000(03)00120-XzbMath1072.68076OpenAlexW4213277474MaRDI QIDQ5917586

Demetrios Achlioptas, Moore, Cristopher

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00120-x

zbMATH Keywords

Random graphsGraph coloringThreshold phenomenaRegular random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Information-theoretic thresholds from the cavity method ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Lower bounds on the chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ The cook-book approach to the differential equation method ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Between 2- and 3-colorability ⋮ A case study in programming a quantum annealer for hard operational planning problems ⋮ On the chromatic number of a random 5-regular graph ⋮ When does the giant component bring unsatisfiability?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Size and connectivity of the \(k\)-core of a random graph
• The asymptotic number of labeled graphs with given degree sequences
• Differential equations for random processes and random graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• A note on the non-colorability threshold of a random graph
• Coloring Random Graphs
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Almost all graphs with 1.44n edges are 3-colorable
• New methods to color the vertices of a graph
• A critical point for random graphs with a given degree sequence
• Studying Balanced Allocations with Differential Equations
• Solutions of ordinary differential equations as limits of pure jump markov processes
• Stable husbands
• Analyses of load stealing models based on families of differential equations