Small hard-to-color graphs for the Sl algorithm

For a graph, a smallest-last (SL) ordering is formed by iteratively deleting a vertex with smallest degree, then reversing the resulting list. The SL algorithm applies greedy coloring to a SL ordering. For a given vertex coloring algorithm, a graph is hard-to-color (HC) if every implementation of the algorithm results in a nonoptimal coloring. In 1997, Kubale et al. showed that \(C₈²\) is the unique smallest HC graph for the SL algorithm. Extending this, we show that for \(k≥4\), \(k+4\) is the smallest order of a HC graph for the SL algorithm with \(χ(G)=k\). We also present a HC graph for the SL algorithm with \(χ(G)=3\) that has order 10.