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

Dimitris Achlioptas Cristopher Moore

Published in: STOC (2002)

Keyphrases

average degree
phase transition
random walk
small world networks
network size
undirected graph
constraint satisfaction
small world
scale free
adjacency matrix
social networks
search algorithm
approximation algorithms