Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ. Issue 3 (16th April 2014) - King, Andrew D.; Reed, Bruce A.
Abstract The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzg59j" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />χ≤⌈12(Δ+1+ω)⌉</alternatives>. In this article, 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‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs.