Claw-free graphs. IV: Decomposition theorem

DOI10.1016/J.JCTB.2007.06.007zbMath1152.05038OpenAlexW2137216672MaRDI QIDQ947722

Maria Chudnovsky, P. D. Seymour

Publication date: 7 October 2008

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2007.06.007

zbMATH Keywords

decompositioninduced subgraphsclaw-free graphs

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items (33)

Clique-coloring of \(K_{3,3}\)-minor free graphs ⋮ A note on the shameful conjecture ⋮ Clique-coloring claw-free graphs ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ The equivalence number of a line graph ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Hereditary Efficiently Dominatable Graphs ⋮ List-Coloring Claw-Free Graphs with $\Delta-1$ Colors ⋮ Claw-free graphs. VII. Quasi-line graphs ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ Graphs of separability at most 2 ⋮ On graphs with no induced subdivision of \(K_4\) ⋮ Unnamed Item ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Claw-free graphs. III: Circular interval graphs ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey ⋮ Claw-free graphs. V. Global structure ⋮ Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs ⋮ Unnamed Item ⋮ On a conjecture on total domination in claw-free cubic graphs ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Gear composition and the stable set polytope ⋮ Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition ⋮ On the Stable Set Polytope of Claw-Free Graphs

Cites Work

• The strong perfect graph theorem
• Claw-free graphs. III: Circular interval graphs
• Bull-free Berge graphs are perfect
• Claw-free graphs. I: Orientable prismatic graphs
• Claw-free graphs. II: Non-orientable prismatic graphs
• The Factorization of Linear Graphs

This page was built for publication: Claw-free graphs. IV: Decomposition theorem