Why Almost All k-Colorable Graphs Are Easy to Color |
| |
Authors: | Amin Coja-Oghlan Michael Krivelevich Dan Vilenchik |
| |
Affiliation: | 1. School of Informatics, University of Edinburgh, Edinburgh, UK 2. School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel-Aviv University, Tel-Aviv, 69978, Israel 3. Department of Mathematics, UCLA, Los Angeles, CA, 90095, USA
|
| |
Abstract: | Coloring a k-colorable graph using k colors (k≥3) is a notoriously hard problem. Considering average case analysis allows for better results. In this work we consider the
uniform distribution over k-colorable graphs with n vertices and exactly cn edges, c greater than some sufficiently large constant. We rigorously show that all proper k-colorings of most such graphs lie in a single “cluster”, and agree on all but a small, though constant, portion of the vertices.
We also describe a polynomial time algorithm that whp finds a proper k-coloring of such a random k-colorable graph, thus asserting that most such graphs are easy to color. This should be contrasted with the setting of very
sparse random graphs (which are k-colorable whp), where experimental results show some regime of edge density to be difficult for many coloring heuristics. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|