Problem 842

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$ ?

Source: erdosproblems.com/842

Graph theory
Chromatic number

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

FlSt92: Fleischner, Herbert and Stiebitz, Michael, A solution to a colouring problem of P. Erdős. Discrete Math. 101 (1992), 39–48; Theorem 1.1, printed p. 39; the reduction and Theorem 2.1, p. 43; the proof, pp. 44–47. Library home: Fleischner and Stiebitz 1992. The article is in the publisher's open archive.
Sa93: Sachs, H., Elementary proof of the cycle-plus-triangles theorem. In Combinatorics, Paul Erdős is Eighty, vol. I (1993), 347–359.
Sa94: Sachs, H., Elementary proof of the cycle-plus-triangles theorem. Les Cahiers du GERAD G-94-02 (February 1994), 15 pp. The exact report bytes and their relation to the 1993 chapter have not been verified.
BK17: Bérczi, Kristóf and Kobayashi, Yusuke, An algorithm for identifying cycle-plus-triangles graphs. Discrete Appl. Math. 226 (2017), 10–16. The Crossref record is bibliographic metadata only.

Problem 842

Status

Proof claims

Discussion