Transitive orientations in bull-reducible Berge graphs

DOI10.1016/J.DAM.2010.05.011MaRDI QIDQ531595zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Cláudia Villela Maciel, Celina M. H. de Figueiredo

Publication date 19 April 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.4522

zbMATH Keywords

perfect graphcoloringcomparability graphbull-reducible graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: A bull is a graph with five vertices $r,y,x,z,s$ and five edges $ry$, $yx$, $yz$, $xz$, $zs$. A graph $G$ is bull-reducible if no vertex of $G$ lies in two bulls. We prove that every bull-reducible Berge graph $G$ that contains no antihole is weakly chordal, or has a homogeneous set, or is transitively orientable. This yields a fast polynomial time algorithm to color exactly the vertices of such a graph.

Recommendations

• The perfection and recognition of bull-reducible Berge graphs
• Optimizing Bull-Free Perfect Graphs
• scientific article; zbMATH DE number 5130731
• On the structure of bull-free perfect graphs. II: The weakly chordal case
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 5130731 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• Algorithm Theory - SWAT 2004
• Algorithmic graph theory and perfect graphs
• Bull-free Berge graphs are perfect
• Bull-free weakly chordal perfectly orderable graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Efficient and practical algorithms for sequential modular decomposition
• Efficient graph representations
• Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
• Flots et tensions dans un graphe
• Improved algorithms for weakly chordal graphs
• Modular decomposition and transitive orientation
• On the structure of bull-free perfect graphs
• On the structure of bull-free perfect graphs. II: The weakly chordal case
• Optimizing Bull-Free Perfect Graphs
• Recognizing Berge graphs
• Recognizing bull-free perfect graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• The perfection and recognition of bull-reducible Berge graphs
• The strong perfect graph theorem
• Transitiv orientierbare Graphen
• Weakly triangulated graphs

Cited in

(2)

• On transitive orientations with restricted covering graphs
• The perfection and recognition of bull-reducible Berge graphs

This page was built for publication: Transitive orientations in bull-reducible Berge graphs

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