A LOCAL STRENGTHENING OF REED'S w, Δ, χ CONJECTURE FOR QUASI-LINE GRAPHS.

Reed's w, Δ, χ conjecture proposes that every graph satisfies χ ≤ [1/2(Δ + 1 + w)] 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²) for line graphs and O(n³m²) 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. [ABSTRACT FROM AUTHOR]