Recognizing bull-free perfect graphs

DOI10.1007/BF01929485zbMath0832.05039WikidataQ64012590 ScholiaQ64012590MaRDI QIDQ1895822

Najiba Sbihi, Bruce A. Reed

Publication date: 20 February 1996

Published in: Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

chromatic numberstrong perfect graph conjecturerecognition algorithmbullbull-free perfect graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

The homogeneous set sandwich problem ⋮ On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Path parity and perfection ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ A Robinson-Schensted algorithm for a class of partial orders ⋮ A maximum degree theorem for diameter-2-critical graphs ⋮ Classes of perfect graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Some properties of edge intersection graphs of single-bend paths on a grid ⋮ Polynomial cases for the vertex coloring problem ⋮ Total domination edge critical graphs with total domination number three and many dominating pairs ⋮ On the structure of bull-free perfect graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Transitive orientations in bull-reducible Berge graphs ⋮ The perfection and recognition of bull-reducible Berge graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ The structure of bull-free graphs I -- three-edge-paths with centers and anticenters ⋮ Complexity of clique-coloring odd-hole-free graphs ⋮ The Structure of Bull-Free Perfect Graphs ⋮ Unnamed Item ⋮ Bull-Reducible Berge Graphs are Perfect

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Weakly triangulated graphs
• Bull-free Berge graphs are perfect
• Star-cutsets and perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs

This page was built for publication: Recognizing bull-free perfect graphs