Logo
All Random Solved Random Open
SOLVED
Let $G$ be a graph on $3n$ vertices formed by taking $n$ vertex disjoint triangles and adding a Hamiltonian cycle (with all new edges) between these vertices. Does $G$ have chromatic number at most $3$?
The answer is yes, proved by Fleischner and Stiebitz [FlSt92].