Transitive orientations in bull-reducible Berge graphs

Simple item page
dc.creatorde Figueiredo, Celina
dc.creatorMaffray, Frederic
dc.creatorMaciel, Claudia Villela
dc.date2008-10-24
dc.date.accessioned2026-07-07T10:13:06Z
dc.date.available2026-07-07T10:13:06Z
dc.descriptionA 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.
dc.identifierhttps://arxiv.org/abs/0810.4522
dc.identifierhttp://arxiv.org/abs/0810.4522
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/172409
dc.subjectCombinatorics
dc.subject05C17 ; 05C75
dc.titleTransitive orientations in bull-reducible Berge graphs
dc.typetext

Files

Collections

arXiv