Edge coloring a cycle plus triangles graph and a stronger problem

Question

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?

ANSWER: (2019 november 23) NOT in general ... see answer 2. It remains to find an example which is 3 connected. Also, the complexity of finding the chromatic index of these graphs is to be determined ... it should be NP complete, perhaps???

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

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.

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.

Answer 1

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:

Answer 2

Here is an example that shows the answer to original question is no. The graph shown has chromatic index 5.

In retrospect, this should have been found earlier. It remains to find a 3-connected counterexample and to establish the complexity of finding the chromatic index of these graphs