Almost all graphs with average degree 4 are 3-colorable.

Dimitris Achlioptas Cristopher Moore

Published in: J. Comput. Syst. Sci. (2003)

Keyphrases

average degree
phase transition
random walk
small world networks
network size
undirected graph
adjacency matrix
heuristic search
constraint satisfaction
connected components
small world