A solution to a colouring problem of P. Erdős (Q1197012)

The authors prove a conjecture made by Paul Erdős at the Julius Petersen Graph Theory Conference at Hindsgavl in July 1990: Any 4-regular graph on \(3n\) vertices which has a decomposition into a Hamiltonian circuit and \(n\) pairwise vertex-disjoint triangles has chromatic number 3. As a consequences, such a graph has independence number \(n\), as conjectured by D. Z. Du and D. F. Hsu in 1987. It was also noted in \textit{M. R. Fellows} [SIAM J. Discrete Math. 3, No. 2, 206-215 (1990; Zbl 0735.05057)] that Erdős' conjecture is equivalent to an old conjecture of Schur, that for any partition of the integers into triples there is another partition of the integers into 3 parts such that each part contains a member of each triple, but no pair of consecutive integers. Thus did the authors kill three birds with one stone. Hopefully the monetary reward customarily offered by Prof. Erdős will be commensurate with the scope of the result.