Sequential colorings and perfect graphs (Q1293205)

The sequential-X algorithm is an algorithm for coloring the vertices of graph \(G\) which, given an ordering \(v_1,\dots, v_n\), colors the vertices of \(G\) greedily using the idea of bichromatic interchange. Clearly, every graph has an ordering such that every execution of the sequential-X algorithm on this ordering provides a chromatic coloring. An ordering of the vertices is called sequential-X perfect if for each induced ordered subgraph the sequential-X perfect algorithm produces an optimal coloring. Furthermore, a vertex \(v\) of \(G\) is called excellent if it does not lie in an odd hole of \(G\) and its neighborhood contains no induced \(P_4\), \(3K_2\) or \(P_3+ K_2\). An ordering \(v_1,\dots, v_n\) of the vertices of graph \(G\) is called excellent if \(v_i\) is excellent in the subgraph of \(G\) induced by \(v_1,\dots, v_i\). The authors show that the sequential-X algorithm when applied to \(G\) with an excellent ordering provides a coloring with \(\omega(G)\) colors. This implies that any excellent ordering is sequential-X perfect. They conclude with a polynomial algorithm which, given a graph \(G\), either answers that \(G\) has no excellent ordering or gives an \(\omega(G)\)-coloring (even if \(G\) has no excellent ordering).