Transitive orientations in bull-reducible Berge graphs ?
A bull is a graph with five vertices r,y,x,z,s r , y , x , z , s and five edges ry r y , yx y x , yz y z , xz x z , zs z s . A graph G G is bull-reducible if every vertex of G G lies in at most one bull of G G . We prove that every bull-reducible Berge graph G 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 the vertices of such a graph exactly.
coloring perfect graph comparability graph bull-reducible graph