The smallest hard-to-color graph for the SL algorithm (Q1356706)

Let \(G=(V(G),E(G))\) be connected simple graph. The smallest-last (SL) sequential graph-colouring algorithm [\textit{D. W. Matula}, \textit{G. Marble} and \textit{J. D. Isaacson}, Graph coloring algorithms, Graph Theory Comput., 109-122 (1972; Zbl 0256.05108)] consists of two steps. Step 1: Arrange \(V(G)\) in the order \(v_1,\dots,v_n\) so that for each \(i=1,\dots,n\), \(v_i\) is one of the vertices with the fewest neighbours \(v_j\) for \(j<i\). Step 2: Colour the vertices so that for each \(i=1,\dots,n\), the colour \(c(v_i)\) is the smallest positive integer not assigned to a vertex \(v_j\) \((j<i)\) adjacent to \(v_i\). The ordering obtained by Step 1 depends upon the choice made to break ties. \(G\) is said to be hard to colour (HC) if for every ordering obtainable by Step 1, Step 2 yields a non-optimal colouring, and slightly hard to colour (SHC) if for at least one of the orderings obtainable by Step 1, Step 2 yields a non-optimal colouring. The graph \(G\) is said to be smaller than the graph \(H\) if either \(|V(G)|<|V(H)|\) or else \(|V(G)|=|V(H)|\) and \(|E(G)|<|E(H)|\). It is shown here that the (triangular) prism is the unique smallest HC graph for SL and the prismatoid (square anti-prism) is the unique smallest SHC graph for SL. This result extends the catalogue of smallest HC and SHC graphs begun in [\textit{P. Hansen} and \textit{J. Kuplinsky}, The smallest hard-to-color graph, Discrete Math. 96, No. 3, 199-212 (1991; Zbl 0759.05038)] for the largest-first algorithm and continued in [\textit{M. Kubale} and \textit{J. Pakulski}, A catalogue of the smallest hard-to-color graphs, Operations research proceedings 1994, Berlin: Springer-Verlag, 133-138 (1995; Zbl 0828.90133)].