2014/04/16 by Andrew D. King, Bruce A. Reed · 11 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs #Mathematics #Combinatorics #Conjecture #Claw #Homogeneous #Complement (music) #Graph #Discrete mathematics #Pathwidth #Indifference graph #Strong perfect graph theorem #Chordal graph #1-planar graph #Line graph
paper · doi:10.1002/jgt.21797
published in Journal of Graph Theory 78(3), 157-194 (Wiley)
openalex publication_date 2014/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25
Abstract The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . 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.