Transitive orientations in bull-reducible Berge graphs Original Research Article

A bull is a graph with five vertices image and five edges image, image, image, image, image. A graph image is bull-reducible if every vertex of image lies in at most one bull of image. We prove that every bull-reducible Berge graph image 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.