Abstract
Reed's ω, δ, χ conjecture proposes that every graph satisfies χ ≤ [1/2(δ + 1 + ω)]; 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(n2) for line graphs and O(n 3m2) 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.
Original language | English (US) |
---|---|
Pages (from-to) | 95-108 |
Number of pages | 14 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 27 |
Issue number | 1 |
DOIs | |
State | Published - 2013 |
All Science Journal Classification (ASJC) codes
- General Mathematics
Keywords
- Chromatic number
- Graph coloring
- Line graph
- Quasi-line graph
- Reed's conjecture