The structure of bull-free graphs I -- three-edge-paths with centers and anticenters

DOI10.1016/j.jctb.2011.07.003zbMath1237.05137OpenAlexW2096613302MaRDI QIDQ765202

Maria Chudnovsky

Publication date: 19 March 2012

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.2011.07.003

zbMATH Keywords

decomposition theoremsinduced subgraphsbull-free graphsgraph structure

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17)

Related Items (16)

Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ On graphs with 2 trivial distance ideals ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Graphs of separability at most 2 ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Odd Holes in Bull-Free Graphs ⋮ Total domination edge critical graphs with total domination number three and many dominating pairs ⋮ Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Graphs without five-vertex path and four-vertex cycle ⋮ Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ The structure of bull-free graphs II and III -- a summary ⋮ The Structure of Bull-Free Perfect Graphs ⋮ Partitioning a graph into disjoint cliques and a triangle-free graph

Cites Work

• Claw-free graphs. VI: Colouring
• On the structure of bull-free perfect graphs
• Ramsey-type theorems
• The structure of bull-free graphs II and III -- a summary
• The strong perfect graph theorem
• The Erdős-Hajnal conjecture for bull-free graphs
• Claw-free graphs. V. Global structure
• Bull-free Berge graphs are perfect
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Recognizing bull-free perfect graphs
• Recognizing Berge graphs
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Coloring Bull-Free Perfectly Contractile Graphs
• Optimizing Bull-Free Perfect Graphs
• Berge trigraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The structure of bull-free graphs I -- three-edge-paths with centers and anticenters