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). [![CYCLE PLUS TRIANGLES GRAPH WITH 10 TRIANGLES][1]][1] Here is a graph with 11 triangles and its Hamiltonian decomposition: [![C + T graph with 11 triangles and its Hamiltonian decomposition][2]][2] [1]: https://i.sstatic.net/l5W5S.png [2]: https://i.sstatic.net/wkS4I.png