Skip to main content
1 of 11
EGME
  • 1k
  • 8
  • 14

I have a partial answer and an attempt to produce a counterexample. In the positive direction, Fournier’s theorem provides a partial answer.

Fournier’s theorem is a generalization 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.

In the negative, I am trying to check whether the following might be a counterexample (it would be great is someone with suitable software can check this). Construct the following C+T graph $G$. Use two triangles, and lay them out on the circuit so that their vertices are alternating. Is this edge-4-colorable? It might be easier to check the vertex-4-colorability of the line graph of $G$. Now take the line graph of this graph $G$, call it $L$. $L$ looks like six copies of $K_4$ such that each such complete graph intersects 4 others, each at a different vertex. I don’t see that $L$ contains a subgraph isomorphic to $K_5$. I haven’t succeeded in coloring any of these two graphs by hand and there are too many color combinations to check them all by hand. Would someone be able and willing to check this example with some suitable software?

EGME
  • 1k
  • 8
  • 14