Coloring Claw-Free Graphs with \Delta-1 Colors

DOI10.1137/12088015XMaRDI QIDQ5300509zbMATH OpenOpenAlexFDO

Authors Daniel W. Cranston, Landon Rabern

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/1206.1269

zbMATH Keywords

Borodin-Kostochka conjectureclaw-freecoloringlist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We prove that every claw-free graph $G$ that doesn't contain a clique on $Delta(G)geq9$ vertices can be $Delta(G)-1$ colored.

Cited in

(29)

• An approximation result for the interval coloring problem on claw-free chordal graphs
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Total coloring of claw-free planar graphs
• Coloring vertices of claw-free graphs in three colors
• Painting squares in \(\Delta^2-1\) shades
• Clique-coloring claw-free graphs
• Graphs with \(\chi=\Delta\) have big cliques
• Brooks' Theorem and Beyond
• Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices
• List-coloring claw-free graphs with -1 colors
• Coloring Graphs with Dense Neighborhoods
• scientific article; zbMATH DE number 5179133 (Why is no real title available?)
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• A note on \(\Delta\)-critical graphs
• Large cliques in graphs with high chromatic number
• Special issue in honour of Landon Rabern
• Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors
• Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
• Borodin-Kostochka conjecture holds for odd-hole-free graphs
• Borodin-Kostochka conjecture holds for \(\overline{K_{1 , 3}} \)-free graphs
• Borodin-Kostochka's conjecture on \(\{P_2 \cup P_3, C_4\}\)-free graphs
• Chromatic-choosability of hypergraphs with high chromatic number
• On the (1, 2⁵)-packing edge-colorings of claw-free subcubic graphs
• The chromatic number of \(\{P_2 \cup P_3,\text{ banner}\}\)-free graphs
• Borodin-Kostochka's conjecture on \(\{P_2\cup P_3, \,\,\text{gem, banner}\}\)-free graphs
• The chromatic number of odd-hole-free graphs
• -boundedness and related problems on graphs without long induced paths: a survey
• On the chromatic number of \(\{\text{bull, diamond}\}\)-free graphs

This page was built for publication: Coloring Claw-Free Graphs with $\Delta-1$ Colors

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