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

We consider colouring the vertices of a graph \(G\) in some order. Let \(\sigma\) be some such ordering, then if we colour in the order \(\sigma\), giving each vertex the smallest colour not on any previous neighbour of it (which of course yields a proper colouring), we will use some number \(\chi(G,\sigma)\) of colours. It is well-known that the chromatic number \(\chi(G)\) is the minimum of \(\chi(G,\sigma)\) over all orderings \(\sigma\). However, the Grundy number \(\Gamma(G)\) the maximum of \(\chi(G,\sigma)\) over all orderings, can be much larger: a classic example is a complete bipartite graph \(K_{n,n}\) with a perfect matching removed which has \(\chi(G)=2\) but \(\Gamma(G)=n\).\N\NWe can also restrict to connected orderings, where (if the vertex ordering is \(v_{1},v_{2},\ldots, v_{m}\)) the subgraph induced by \(v_{1},v_{2},\ldots ,v_{i}\) is connected for each \(1\leq i\leq n\). We let \(\chi_{c}(G)\) be the minimum, over all connected orderings, of \(\chi(G,\sigma)\). In [\textit{F. Benevides} et al., Lect. Notes Comput. Sci. 8392, 433--441 (2014; Zbl 1405.68126)], it is shown that for every \(k\geq 3\) there is a \(k\)-chromatic graph with \(\chi_{c}(G)>\chi(G)\). However, for every graph, we have \(\chi_{c}(G)\leq \chi(G)+1\) and deciding if \(\chi_{c}(G)=\chi(G)\) is hard. There is also a connected Grundy number \(\Gamma_{c}(G)\) which is the maximum, over all connected orderings, \(\sigma\) of \(\chi(G,\sigma)\).\N\NFollowing [\textit{N.-K. Le} and \textit{N. Trotignon}, ``Connected greedy colouring in claw-free graphs'', Preprint \url{arXiv:1805.01953}], a graph is said to be good if any connected ordering gives an optimal colouring, i.e. \(\Gamma_{c}(G)=\chi(G)\), otherwise it is bad. A particularly severe form of badness is when no connected ordering gives an optimal colouring when the graph is said to be ugly. Ugly graphs exist, including planar cubic ugly graphs, claw-free ugly graphs and ugly graphs of arbitrarily large girth.\N\NOne main result of the paper under review is that no perfect graph is ugly. A general proof of this is given, but also simpler proofs are given for some special classes of perfect graphs such as block graphs and comparability graphs, and it is also shown that no \(K_{4}\)-minor free graph is ugly. The proofs are constructive and imply polynomial-time algorithms to compute good connected orderings for these classes.