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

DOI10.1016/J.JCTB.2011.07.003MaRDI QIDQ765202zbMATH OpenOpenAlexFDO

Authors 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

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)

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

Cites work

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

Cited in

(20)

• Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the \(H_{6}\)-conjecture
• 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
• The Doyen-Wilson theorem for bull designs
• 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
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• The structure of bull-free graphs II and III -- a summary
• 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
• Partitioning a graph into disjoint cliques and a triangle-free graph
• On graphs with 2 trivial distance ideals
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Transitive orientations in bull-reducible Berge graphs
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Graphs without five-vertex path and four-vertex cycle

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)