Skip to main content
5 of 11
deleted 1 character in body
EGME
  • 1k
  • 8
  • 14

I have a partial answer and I am attempting to produce a counterexample (I need to learn how to use the new package I am using for this productively). 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.

The small examples with a couple of triangles that I have checked now with a computer are class 1. With a random C+T graph generator and a chromatic index calculator, I can verify that many (all that I have tried) C+T graphs with several triangles, (say 10, or however many is reasonable to compute) are of class 1. It seems like a safe bet that the question asked has an affirmative answer. I can now generate hundreds (thousands) of these and check them almost instantly.

Here is a pretty picture of a C + T graph with 10 triangles

CYCLE PLUS TRIANGLES GRAPH WITH 10 TRIANGLES

Note that double edges are not allowed ... the graph has to be simple

EGME
  • 1k
  • 8
  • 14