← All problems

Erdős Problem #842 — Three-colouring triangles joined by a Hamiltonian cycle

34 years old · traced to

Let nn be a positive integer, let VV be a set of 3n3n vertices, and let T1,…,TnT_1,\ldots,T_n be pairwise vertex-disjoint triangles whose vertex sets partition VV. Let CC be a Hamiltonian cycle on VV such that none of its edges is an edge of any TiT_i. Form the graph GG 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

E(G)=E(C)∪⋃i=1nE(Ti),E(C)∩⋃i=1nE(Ti)=∅.E(G)=E(C)\cup\bigcup_{i=1}^n E(T_i),\qquad E(C)\cap\bigcup_{i=1}^n E(T_i)=\varnothing.

Erdős Problem #842 Bérczi and Kobayashi, An algorithm for identifying cycle-plus-triangles graphs

Is GG always 3-colourable, that is, does every such GG satisfy χ(G)≤3\chi(G)\leq 3? 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 nn. 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.

Source: P. Erdős, Some of my favourite problems in various branches of combinatorics, Le Matematiche 47 (1992), no. 2, 231–240.

Progress summary

Never refreshed

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.