Properly orderable graphs (Q1815322)

In a graph \(G\) provided with a linear order \(<\) on \(V(G)\), a chordless path with vertices \(a\), \(b\), \(c\), \(d\) and edges \(ab\), \(bc\), \(cd\) is called an obstruction if both \(a<b\) and \(d<c\) hold. \textit{V. Chvátal} [Perfect graphs, Ann. Discrete Math. 21, 63-65 (1984; Zbl 0559.05055)] defined the class of perfectly orderable graphs, i.e., graphs possessing an acyclic orientation of the edges such that no obstruction is induced, and proved that they are perfect. In this paper, the class of properly orderable graphs is introduced, which is a generalization of Chvátal's class of perfectly orderable graphs since obstructions are forbidden only in the subgraphs induced by the vertices of an odd cycle. The perfection of these graphs is proved, and an \(O(m^2+mn+n)\) optimal colouring algorithm for the class of properly orderable graphs of order \(n\) and size \(m\) is given.