Name
Abstract | ||
|---|---|---|
Reed's omega, Delta, chi conjecture proposes that every graph satisfies chi <= inverted right perpendicular1/2 (Delta + 1 + omega)inverted left perpendicular; it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colorings that achieve our bounds: O(n(2)) for line graphs and O(n(3)m(2)) for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a coloring that achieves the bound of Reed's original conjecture. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/110847585 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
graph coloring,chromatic number,line graph,quasi-line graph,Reed's conjecture | Discrete mathematics,Indifference graph,Combinatorics,Line graph,Chordal graph,Mathematical proof,Pathwidth,Conjecture,1-planar graph,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
27 | 1 | 0895-4801 |
Citations | PageRank | References |
5 | 0.57 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Andrew D. King | 2 | 192 | 18.88 |
| Matthieu Plumettaz | 3 | 97 | 4.96 |
| Paul D. Seymour | 4 | 2786 | 314.49 |