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

DOI10.1137/110847585zbMath1267.05116arXiv1109.2112OpenAlexW2963922749WikidataQ123282682 ScholiaQ123282682MaRDI QIDQ5300483

Maria Chudnovsky, Matthieu Plumettaz, Andrew D. King, P. D. 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

graph coloringline graphchromatic numberReed's conjecturequasi-line graph

Mathematics Subject Classification ID

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

Related Items

Combinatorics. Abstracts from the workshop held January 1--7, 2023, Large cliques in graphs with high chromatic number, Short Fans and the 5/6 Bound for Line Graphs, A superlocal version of Reed's conjecture, On bounding the difference of the maximum degree and the clique number, Corrigendum to: ``A local epsilon version of Reed's conjecture, A local epsilon version of Reed's conjecture, Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ, Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition