quasi-line graphs
Maria Chudnovsky, Andrew D. King, Matthieu Plumettaz, Paul D. Seymour · 2011
Reed's !, , conjecture proposes that every graph satises d 1 ( + 1 + !)e; 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 con- structing colourings 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 colouring that achieves the bound of Reed's original conjecture.