Skip to main content

A LOCAL STRENGTHENING OF REED’S omega, Delta, chi CONJECTURE FOR QUASI- LINE GRAPHS

Author(s): Chudnovsky, Maria; King, Andrew D; Plumettaz, Matthieu; Seymour, Paul D

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1nh36
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.
Publication Date: 2013
Electronic Publication Date: 17-Jan-2013
Citation: Chudnovsky, Maria, King, Andrew D, Plumettaz, Matthieu, Seymour, Paul. (2013). A LOCAL STRENGTHENING OF REED’S omega, Delta, chi CONJECTURE FOR QUASI- LINE GRAPHS. SIAM JOURNAL ON DISCRETE MATHEMATICS, 27 (95 - 108. doi:10.1137/110847585
DOI: doi:10.1137/110847585
ISSN: 0895-4801
Pages: 95 - 108
Type of Material: Journal Article
Journal/Proceeding Title: SIAM JOURNAL ON DISCRETE MATHEMATICS
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.