# Edge coloring a cycle plus triangles graph and a stronger problem

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:

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