A local strengthening of reed's ω, δ, χ conjecture for quasi-line graphs

Maria Chudnovsky, Andrew D. King, Matthieu Plumettaz, Paul Seymour

Research output: Contribution to journalArticle

8 Scopus citations

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 languageEnglish (US)
Pages (from-to)95-108
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume27
Issue number1
DOIs
StatePublished - May 6 2013

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Chromatic number
  • Graph coloring
  • Line graph
  • Quasi-line graph
  • Reed's conjecture

Fingerprint Dive into the research topics of 'A local strengthening of reed's ω, δ, χ conjecture for quasi-line graphs'. Together they form a unique fingerprint.

  • Cite this