✦ LIBER ✦

Why Almost Allk-Colorable Graphs Are Easy to Color

✍ Scribed by Amin Coja-Oghlan; Michael Krivelevich; Dan Vilenchik

Publisher: Springer
Year: 2009
Tongue: English
Weight: 910 KB
Volume: 46
Category: Article
ISSN: 1433-0490
DOI: 10.1007/s00224-009-9231-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Almost all k-colorable graphs are easy t

Almost all k-colorable graphs are easy to color

✍ Jonathan S Turner 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 972 KB

Almost all graphs with average degree 4

Almost all graphs with average degree 4 are 3-colorable

✍ Dimitris Achlioptas; Cristopher Moore 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 323 KB

We analyze a randomized version of the Brelaz heuristic on sparse random graphs. We prove that almost all graphs with average degree dp4:03; i.e., Gðn; p ¼ d=nÞ; are 3-colorable and that a constant fraction of all 4-regular graphs are 3-colorable.