Almost all graphs of degree 4 are 3-colorable

Cris Moore

University of New Mexico and the Santa Fe Institute

April 26,
refreshments at 3:45pm


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 3-coloring. 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 4-regular graphs are 3-colorable. 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.

Speaker's Contact Info: moore(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on March 25, 2002 at 06:16 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.