Claw-free graphs, skeletal graphs, and a stronger conjecture on , , and

DOI10.1002/JGT.21797MaRDI QIDQ4982280zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andrew D. King, Bruce Reed

Publication date 24 March 2015

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.3036

zbMATH Keywords

chromatic numbergraph coloringclaw-free graphReed's conjecture

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The second author's $omega$, $Delta$, $chi$ conjecture proposes that every graph satisties $chileqlceilfrac12(Delta+1+omega)ceil$. 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.

Recommendations

• Claw-free graphs. VI: Colouring
• On the choosability of claw-free perfect graphs
• Squared chromatic number without claws or large cliques
• An approximate version of Hadwiger's conjecture for claw-free graphs
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• A Note On Reed's Conjecture
• A description of claw-free perfect graphs
• A strengthening of Ben Rebea's lemma
• A superlocal version of Reed's conjecture
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• An algorithm for finding homogeneous pairs
• An upper bound for the chromatic number of line graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Claw-free graphs. I: Orientable prismatic graphs
• Claw-free graphs. II: Non-orientable prismatic graphs
• Claw-free graphs. V. Global structure
• Claw-free graphs. VI: Colouring
• Coloring quasi-line graphs
• Gear composition and the stable set polytope
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Paths, Trees, and Flowers
• Recognizing claw-free perfect graphs
• The round-up property of the fractional chromatic number for proper circular arc graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited in

(5)

• Colouring squares of claw-free graphs
• A local epsilon version of Reed's conjecture
• A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\)
• A note on Reed's conjecture for triangle-free graphs
• Colouring squares of claw-free graphs

This page was built for publication: Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)

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