Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly

The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering σ= v₁,,vₙ, the "First-Fit" greedy colouring algorithm colours the vertices in the order of σ by assigning to each vertex the smallest colour unused in its neighbourhood. By restricting this procedure to vertex orderings that are connected, we obtain { connected greedy colourings}. For some graphs, all connected greedy colourings use exactly χ(G) colours; they are called { good graphs}. On the opposite, some graphs do not admit any connected greedy colouring using only χ(G) colours; they are called { ugly graphs}. We show that no perfect graph is ugly. We also give simple proofs of this fact for subclasses of perfect graphs (block graphs, comparability graphs), and show that no K₄-minor free graph is ugly. Moreover, our proofs are constructive, and imply the existence of polynomial-time algorithms to compute good connected orderings for these graph classes.