Bull-Free Weakly Chordal Perfectly Orderable Graphs

Abstract.

 Using doubly lexical orders and the notion of box partition due to de Figueiredo, Maffray, and Porto, we show that a certain subclass of bull-free weakly chordal graphs is perfectly orderable. This together with results of de Figueiredo, Maffray, and Porto confirms Chvátal's conjecture that bull-free graphs with no anti-hole and no odd hole are perfectly orderable; here hole means induced cycle with five or more vertices.