Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00224-009-9231-5 | Theory Comput. Syst. |
Keywords | Field | DocType |
cn edge,better result,k-colorable graph,coloring heuristics,proper k-coloring,k-colorable graphs,sparse random graph,average case analysis,proper k-colorings,k-colorable whp,average case analysis · k-colorability · random graphs · spectral analysis,random k-colorable graph,random graph,uniform distribution | Discrete mathematics,Complete coloring,Random regular graph,Edge coloring,Combinatorics,Indifference graph,Chordal graph,Greedy coloring,1-planar graph,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
46 | 3 | 1432-4350 |
Citations | PageRank | References |
6 | 0.57 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| michael krivelevich | 2 | 1688 | 179.90 |
| Dan Vilenchik | 3 | 143 | 13.36 |