Skip to main content
6 of 11
added 4 characters 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.

UPDATE: All examples with even number of triangles that I have tried are class 1. I didn’t realize before that all the examples I had tried had an even number of triangles. HOWEVER, examples with an ODD number of triangles are class 2. So we can CONFIRM that the the conjecture as such does not stand. So it is pertinent to modify the question: are all C + T graphs with an even number of triangles class 1? And are all the ones that have an odd number of triangles class 2?

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