Hard-to-color graphs for connected sequential colorings
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.
scientific article; zbMATH DE number 612426
scientific article