Transitive orientations in bull-reducible graphs

International audienceA previous termbullnext term is a previous termgraphnext term with five vertices r,y,x,z,s and five edges ry, yx, yz, xz, zs. A previous termgraphnext termG is previous termbullnext term-previous termreduciblenext term if every vertex of G lies in at most one previous termbullnext term of G. We prove that every previous termbullnext term-previous termreduciblenext term Berge previous termgraphnext termG 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 previous termgraphnext term exactly