Problem Statement
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$?
Categories:
Graph Theory Chromatic Number
Progress
The answer is yes, proved by Fleischner and Stiebitz [FlSt92].Source: erdosproblems.com/842 | Last verified: January 16, 2026