
The Library
Why almost all k-colorable graphs are easy to color
Tools
Coja-Oghlan, Amin, Krivelevich, Michael and Vilenchik, Dan (2010) Why almost all k-colorable graphs are easy to color. Theory of Computing Systems, Volume 46 (Number 3). pp. 523-565. doi:10.1007/s00224-009-9231-5 ISSN 1432-4350.
![]() |
PDF
kcol.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (910Kb) |
Official URL: http://dx.doi.org/10.1007/s00224-009-9231-5
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.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||
Journal or Publication Title: | Theory of Computing Systems | ||||||
Publisher: | Springer New York LLC | ||||||
ISSN: | 1432-4350 | ||||||
Official Date: | April 2010 | ||||||
Dates: |
|
||||||
Volume: | Volume 46 | ||||||
Number: | Number 3 | ||||||
Page Range: | pp. 523-565 | ||||||
DOI: | 10.1007/s00224-009-9231-5 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 20 December 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |