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

DOI10.1016/J.JCTB.2011.07.003zbMATH Open1237.05137OpenAlexW2096613302MaRDI QIDQ765202FDOQ765202

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

Recommendations

• The structure of bull-free graphs II and III -- a summary
• On the structure of bull-free perfect graphs
• The structure of bull-free perfect graphs
• On the structure of bull-free perfect graphs. II: The weakly chordal case
• A constructive characterization of 3-connected triangle-free graphs
• The structure of \(\{ K_{1,3},Z_2\}\)-free graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• On \(m\)-centers in \(P_ t\)-free graphs
• The 3-connected graphs with exactly three non-essential edges
• Odd holes in bull-free graphs

zbMATH Keywords

induced subgraphsgraph structuredecomposition theoremsbull-free graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Berge trigraphs
• The structure of bull-free graphs II and III -- a summary
• The strong perfect graph theorem
• Claw-free graphs. V. Global structure
• Recognizing Berge graphs
• Recognizing bull-free perfect graphs
• Title not available (Why is that?)
• Ramsey-type theorems
• Optimizing Bull-Free Perfect Graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Bull-free Berge graphs are perfect
• Claw-free graphs. VI: Colouring
• On the structure of bull-free perfect graphs
• Coloring Bull-Free Perfectly Contractile Graphs

Cited In (16)

• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Improved FPT algorithms for weighted independent set in bull-free graphs
• Graphs of separability at most 2
• The structure of bull-free graphs II and III -- a summary
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Odd Holes in Bull-Free Graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• The structure of bull-free perfect graphs
• The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• On graphs with 2 trivial distance ideals
• Graphs without five-vertex path and four-vertex cycle
• 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
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs

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

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