Almost all graphs of degree 4 are 3colorableCris MooreUniversity of New Mexico and the Santa Fe Institute
April 26,

ABSTRACT


A graph coloring is called proper if no two nodes of the same color are connected by an edge. Deciding whether a graph has a proper coloring is a classical problem, of interest in Combinatorics and Computer Science. In this talk we study the probability that a random graph on n vertices with average degree d has a proper 3coloring. This probability decreases as d grows, and it is conjectured that it jumps from 1 to 0 as n tends to infinity, when d passes a threshold t of about 4.7. We survey known results on the subject and prove that t > 4.03. We also show that almost all 4regular graphs are 3colorable. The proof uses analysis of differential equations which arise in the study of a greedy heuristic algorithm for graph coloring. This is joint work with Dimitris Achlioptas, and will appear at the Symposium on the Theory of Computing (STOC) 2002. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

