Recognizing bull-free perfect graphs

DOI10.1007/BF01929485MaRDI QIDQ1895822zbMATH OpenWikidataFDO

Authors Najiba Sbihi, Bruce Reed

Publication date 20 February 1996

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

zbMATH Keywords

chromatic numberrecognition algorithmstrong perfect graph conjecturebullbull-free perfect graphs

Mathematics Subject Classification ID

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

Recommendations

• The structure of bull-free perfect graphs
• On the structure of bull-free perfect graphs
• The perfection and recognition of bull-reducible Berge graphs
• Bull-free Berge graphs are perfect
• Coloring bull-free perfect graphs
• Optimizing Bull-Free Perfect Graphs
• Recognizing claw-free perfect graphs
• Publication:4952598
• Recognizing Dart-Free Perfect Graphs
• scientific article; zbMATH DE number 861423

Cites work

• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Bull-free Berge graphs are perfect
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs
• On rigid circuit graphs
• Star-cutsets and perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Weakly triangulated graphs

Cited in

(32)

• Optimizing Bull-Free Perfect Graphs
• Total domination edge critical graphs with total domination number three and many dominating pairs
• Coloring bull-free perfect graphs
• Bull-free Berge graphs are perfect
• A Robinson-Schensted algorithm for a class of partial orders
• Maximum weight independent sets in classes related to claw-free graphs
• Recognizing Dart-Free Perfect Graphs
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• On the structure of bull-free perfect graphs
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• A maximum degree theorem for diameter-2-critical graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• The perfection and recognition of bull-reducible Berge graphs
• Polynomial cases for the vertex coloring problem
• Some properties of edge intersection graphs of single-bend paths on a grid
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• 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
• Bull-free weakly chordal perfectly orderable graphs
• On the structure of bull-free perfect graphs. II: The weakly chordal case
• A faster algorithm to recognize even-hole-free graphs
• Recognizing Perfect 2-Split Graphs
• Bull-Reducible Berge Graphs are Perfect
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• Complexity of clique-coloring odd-hole-free graphs
• Transitive orientations in bull-reducible Berge graphs
• The homogeneous set sandwich problem
• Classes of perfect graphs
• Path parity and perfection

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

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