Almost All Graphs of Degree 4 are 3-colorable
AbstractThe technique of approximating the mean path of Markov chains by differential equations has proved to be a useful tool in analyzing the performance of heuristics on random graph instances. However, only a small family of algorithms can currently be analyzed by this method, due to the need to maintain uniform randomness within the original state space. Here, we significantly expand the range of the differential equation technique, by showing how it can be generalized to handle heuristics that give priority to high- or low-degree vertices. In particular, we focus on 3-coloring and analyze a "smoothed" version of the practically successful Brelaz heuristic. This allows to prove that almost all graphs with average degree $d$, i.e. $G(n,p=d/n)$, are 3-colorable for $d \leq 4.03$, and that almost all 4-regular graphs are 3-colorable. This improves over the previous lower bound of $3.847$ on the 3-colorability threshold for $G(n,p=d/n)$ and gives the first non-trivial result on the colorability of random regular graphs. In fact, our methods can be used to deal with "arbitrary" sparse degree distributions and in conjunction with general graph algorithms that have a preference for high- or low-degree vertices.
Download InfoTo our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.
Bibliographic InfoPaper provided by Santa Fe Institute in its series Working Papers with number 01-11-070.
Date of creation: Nov 2001
Date of revision:
Contact details of provider:
Postal: 1399 Hyde Park Road, Santa Fe, New Mexico 87501
Web page: http://www.santafe.edu/sfi/publications/working-papers.html
More information through EDIRC
Random graphs; graph coloring; analysis of algorithms; computational complexity; heuristics; phase transitions in NP-complete problems;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2002-03-14 (All new papers)
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Thomas Krichel).
If references are entirely missing, you can add them using this form.