Transitive orientations in bull-reducible Berge graphs

Celina de Figueiredo, Frederic Maffray, Claudia Villela Maciel

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…