A LOCAL STRENGTHENING OF REED%26apos;S omega, Delta, chi CONJECTURE FOR QUASI- LINE GRAPHS

作者：Chudnovsky Maria^*; King Andrew D; Plumettaz Matthieu; Seymour Paul

来源：SIAM Journal on Discrete Mathematics, 2013, 27(1): 95-108.

DOI：10.1137/110847585

• graph coloring
• chromatic number
• line graph
• quasi-line graph
• Reed%26apos
• s conjecture

Reed%26apos;s omega, Delta, chi conjecture proposes that every graph satisfies chi %26lt;= 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%26apos;s original conjecture.

• 出版日期2013