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.

(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).


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.