Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ

DOI10.1002/jgt.21797zbMath1309.05076arXiv1212.3036OpenAlexW1559782353WikidataQ29031799 ScholiaQ29031799MaRDI QIDQ4982280

Andrew D. King, Bruce A. 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

graph coloringclaw-free graphchromatic numberReed's conjecture

Mathematics Subject Classification ID

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

Related Items

A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω, A note on Reed's conjecture for triangle-free graphs, Colouring squares of claw-free graphs, Colouring Squares of Claw-free Graphs, Corrigendum to: ``A local epsilon version of Reed's conjecture, A local epsilon version of Reed's conjecture

Cites Work

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