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

PDF kcol.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (910Kb)

Request Changes to record.

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 > Computer Science Faculty of Science > Mathematics
Journal or Publication Title:	Theory of Computing Systems
Publisher:	Springer New York LLC
ISSN:	1432-4350
Official Date:	April 2010
Dates:	Date Event April 2010 Published 4 August 2009 Available
Date of first compliant deposit:	20 December 2015
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

Request changes or add full text files to a record

Repository staff actions (login required)

View Item