Skip to main content
9 of 11
deleted 466 characters in body
EGME
  • 1k
  • 8
  • 14

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

CYCLE PLUS TRIANGLES GRAPH WITH 10 TRIANGLES

EGME
  • 1k
  • 8
  • 14