Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that induce disjoint triangles (3-circuits). Note $G$ is 4-regular.

UPDATED QUESTION (2019 may 17):

QUESTION: Is $G$ class 1, that is, can it be edge-4-colored, if it has an even number of triangles?

NEW UPDATE (2019 may 20 b): A question of which an affirmative answer implies an affirmative answer to our original question: Does $G$ have a Hamiltonian factorization, that is, are there two edge disjoint spanning cycles in $G$. I haven’t checked this with a computer, but it seems to hold for the small cases. UPDATE: I have now this working in a computer ... I haven’t tested many graphs, but the few I have tested, including some larger ones, seem to have (I write seem because I need to verify my code) Hamiltonian decompositions, including those of odd order. Next I will put this in a loop and test LOTS of random examples. SEE ANSWER FOR PICTURE ..

NOTE: Regarding the Hamiltonian decompositions, it was an open problem until 1997 whether CT graphs had a Hamiltonian circuit other than the obvious one. This was settled affirmatively by Thomassen. But the computer says that, for example, a random CT graph with 12 triangles has about 300 000 (not exact) distinct Hamiltonian circuits. I need to make the tests with a lot more graphs to determine some kind of average.

(SIDE) FACT : If $G$ has an odd number of triangles then it is class 2. This is because a cycle plus triangles graph with an odd number of triangles is a regular graph of odd order ... all such graphs are class 2 (suppose it is class 1 ... then each vertex is incident with an edge of each color. But the edges of a given color are independent, so they are incident with an even number of vertices, while there is an odd number of vertices, contradiction).

The hypothesis that C+T graphs which have an even number of triangles are class 1 is supported by computer experiments.

Cycle plus triangles graphs became well known when Erdös posed the “cycle plus triangles problem” (whether such graphs are vertex-3-colorable). This was solved affirmatively by Fleishner and Stiebitz using the Alon-Tarsi theorem, and later Sachs, inductively.

Perhaps the answer to my question above is known, but I am unaware of it.

In the generalization of this question to “cycle plus even $k$-cliques” (I hope it is clear what this means) the answer is that they are all class 1, as you can edge color the edges of the $k$-cliques with $k$-1 colors, and use two remaining colors for the edges of the even cycle in the ($k$+1)-regular graph. It is tantalizing to speculate that a similar answer as the answer for the “cycles plus triangles” case would hold for the general “cycle plus odd cliques” situation, of which the cycle plus triangles is a special case. It would be nice to settle at least this special case with proofs, if it is not settled already.