Transitive orientations in bull-reducible Berge graphs

DOI10.1016/J.DAM.2010.05.011zbMATH Open1213.05104arXiv0810.4522OpenAlexW2033622089MaRDI QIDQ531595FDOQ531595

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)

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.

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

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

zbMATH Keywords

perfect graphcoloringcomparability graphbull-reducible graph

Mathematics Subject Classification ID

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

Cites Work

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