Bull-free Berge graphs are perfect
A bull is the (self-complementary) graph with \(V(G)=\{a,b,c,d,e\}\) and \(E(G)=\{ab,ac,bc,bd,ce\}\); and a graph G is called Berge if neigher G nor its complement contains a chordless cycle whose length is odd and at least five. Then the Strong Perfect Graph Conjecture is that every Berge graph is perfect. This paper proves that bull-free Berge graphs are perfect. The proof relies on a lemma that no minimal imperfect graph contains a so-called homogeneous pair, which generalizes a result of \textit{Olariu} [`No antitwins in minimal imperfect graphs', J. Comb. Theory (B) to appear)]. The proof also relies on the result of the first author [J. Comb. Theory, Ser. B 39, 189-199 (1985)] that no minimal imperfect graph contains a star-cutset.
- The structure of bull-free perfect graphs
- On the structure of bull-free perfect graphs
- Recognizing bull-free perfect graphs
- Almost all Berge Graphs are Perfect
- The perfection and recognition of bull-reducible Berge graphs
- Coloring bull-free perfect graphs
- Chair-free Berge graphs are perfect
- scientific article; zbMATH DE number 861423
- Optimizing Bull-Free Perfect Graphs
- On the structure of bull-free perfect graphs. II: The weakly chordal case
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Two classes of perfect graphs
- Some properties of minimal imperfect graphs
- Hamiltonicity in claw-free graphs
- Stability number of bull- and chair-free graphs
- On minimal imperfect graphs without induced P₅
- A description of claw-free perfect graphs
- A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
- New classes of Berge perfect graphs
- Path parity and perfection
- A nice class for the vertex packing problem
- Chair-free Berge graphs are perfect
- Recognizing bull-free perfect graphs
- A new class of perfect Hoàng graphs
- On the vertex packing problem
- Most unbreakable murky graphs are bull-free
- Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
- Classes of perfect graphs
- Finding a smallest odd hole in a claw-free graph using global structure
- Decomposing Berge graphs and detecting balanced skew partitions
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
- Skew partitions in perfect graphs
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- The structure of bull-free perfect graphs
- Counting List Matrix Partitions of Graphs
- Amalgams and -boundedness
- Bull-Reducible Berge Graphs are Perfect
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Complexity of clique-coloring odd-hole-free graphs
- The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect
- Substitution and \(\chi\)-boundedness
- The perfection and recognition of bull-reducible Berge graphs
- Computing \(H\)-joins with application to 2-modular decomposition
- scientific article; zbMATH DE number 1445285 (Why is no real title available?)
- 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
- Fast Skew Partition Recognition
- Transitive orientations in bull-reducible Berge graphs
- scientific article; zbMATH DE number 2230220 (Why is no real title available?)
- scientific article; zbMATH DE number 2230322 (Why is no real title available?)
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- On perfect switching classes
- On the structure of bull-free perfect graphs. II: The weakly chordal case
- On perfect switching classes
- A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
- Polynomial cases for the vertex coloring problem
- An algorithm for finding homogeneous pairs
- On the structure of bull-free perfect graphs
- Reuniting -boundedness with polynomial -boundedness
- Combinatorial optimization with 2-joins
- The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
- Algorithmic aspects of switch cographs
- On the closure of triangle-free graphs under substitution
- Graph parameters measuring neighbourhoods in graphs-bounds and applications
- Claw-free graphs. IV: Decomposition theorem
- The Erdős-Hajnal conjecture for bull-free graphs
This page was built for publication: Bull-free Berge graphs are perfect
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095938)
