Erdős Problem #842 — Three-colouring triangles joined by a Hamiltonian cycle
Let be a positive integer, let be a set of vertices, and let be pairwise vertex-disjoint triangles whose vertex sets partition . Let be a Hamiltonian cycle on such that none of its edges is an edge of any . Form the graph by taking the union of these triangles and the cycle; equivalently, Erdős Problem #842 Bérczi and Kobayashi, An algorithm for identifying cycle-plus-triangles graphs
Erdős Problem #842 Bérczi and Kobayashi, An algorithm for identifying cycle-plus-triangles graphs
Is always 3-colourable, that is, does every such satisfy ? Erdős Problem #842 Bérczi and Kobayashi, An algorithm for identifying cycle-plus-triangles graphs
Background
This is the cycle-plus-triangles problem. Du, Hsu, and Hwang conjectured in 1986 that every such graph has an independent set of size . Erdős strengthened the challenge by asking whether every graph in the class is 3-colourable; he included the problem among his favourite combinatorial questions. The colouring assertion is stronger: a proper colouring with three colours gives an independent colour class, while the triangles impose additional structure on all three classes. The Complexity of Finding Fair Independent Sets in Cycles Erdős, Some of my favourite problems in various branches of combinatorics
References
P. Erdős, Some of my favourite problems in various branches of combinatorics, Le Matematiche 47 (1992), no. 2, 231–240.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.