pith. sign in

arxiv: 1212.3036 · v1 · pith:QRIRXEEGnew · submitted 2012-12-13 · 💻 cs.DM · math.CO

Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Delta, and chi

classification 💻 cs.DM math.CO
keywords graphsconjectureclaw-freedeltaomegaproveholdsskeletal
0
0 comments X
read the original abstract

The second author's $\omega$, $\Delta$, $\chi$ conjecture proposes that every graph satisties $\chi \leq \lceil \frac 12 (\Delta+1+\omega)\rceil$. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful $\chi$-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called "skeletal" graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.