A Local Strengthening of Reed's \omega, \Delta, \chi Conjecture for Quasi-line Graphs

DOI10.1137/110847585MaRDI QIDQ5300483zbMATH OpenOpenAlexWikidataFDO

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

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.2112

zbMATH Keywords

chromatic numbergraph coloringline graphReed's conjecturequasi-line graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Abstract: Reed's $omega$, $Delta$, $chi$ conjecture proposes that every graph satisfies $chileqlceilfrac12(Delta+1+omega)ceil$; 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 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.

Recommendations

• Bounding χ in terms of ω and Δ for quasi-line graphs
• The Erdős-Lovász tihany conjecture for quasi-line graphs
• Hadwiger's conjecture for quasi-line graphs
• A note on Reed's conjecture for triangle-free graphs
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• A local characterization of bounded clique-width for line graphs
• On locally quasiconnected graphs and their upper embeddability
• A local epsilon version of Reed's conjecture
• On \((\delta, \chi)\)-bounded families of graphs

Cited in

(11)

• Large cliques in graphs with high chromatic number
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Short fans and the 5/6 bound for line graphs
• Solving the weighted stable set problem in claw-free graphs via decomposition
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• A local epsilon version of Reed's conjecture
• Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)
• Bounding χ in terms of ω and Δ for quasi-line graphs
• A superlocal version of Reed's conjecture
• An upper bound for the chromatic number of line graphs
• On bounding the difference of the maximum degree and the clique number

This page was built for publication: A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300483)