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.


I have a partial answer and I am exploring the problem with a computer now. In the positive direction, Fournier’s theorem provides a partial answer.

Fournier’s theorem is a strengthening of Vizing’s theorem and it goes as follows: Let $D$ be the max degree of your graph $G$. If the vertices of $G$ that have degree $D$ are independent, then $G$ is class 1. Let us say that a graph which satisfies this condition is a Fournier graph.

So consider a cycle plus triangles graph $G$ and vertex-3-color $G$ with colors $r, g, b$. Delete the triangle edges between vertices colored $r, b$. Then, the resulting graph is Fournier with max degree 4, so it can be edge-4-colored. So the question remains whether it is possible to reinsert the deleted edges so that $G$ remains class 1. It turns out, not always (not if there are an odd number of triangles, see the updated question).

All examples with even number of triangles that I have explored are class 1. Recall that we are considering only simple graphs.

Here is a pretty picture of a C + T graph with 10 triangles. I edited the answer to include the correct picture. The previous one had an edge with a 5th color by mistake (my mistake, not the computer).


Here is a graph with 11 triangles and its Hamiltonian decomposition:

C + T graph with 11 triangles and its Hamiltonian decomposition

  • $\begingroup$ @Martin Sleziak Thank you for the question edit $\endgroup$ – EGME May 16 at 13:36

Your Answer

