Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Why almost all k-colorable graphs are easy to color

Tools
- Tools
+ 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.

[img] 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

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, 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:
DateEvent
April 2010Published
4 August 2009Available
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us