Hard-to-color graphs for connected sequential colorings (Q1329800)

A graph \(G\) is said to be hard-to-colour if any connected colouring produces a nonoptimal colouring, and partially hard-to-colour if any such colouring starting in a specified vertex is nonoptimal. The authors show that the linked pair of twin kites with 18 vertices is the smallest cubic hard-to-colour graph and they conjecture that this graph is the smallest graph hard-to-colour from any starting point.