3-edge colorability of planar, triangle-free graphs of maximum degree 3

80 Views Asked by At

I know it will have a 4-edge coloring, from Vizing's theorem. I was able to 3-colour every example I tried to come up with. A preliminary search didn't help me find any results either. Grotzsch's theorem and related others seem to involve vertex coloring, not edge coloring.

I'm specifically interested in this class of graphs as the independent set problem is still NP-complete here.

2

There are 2 best solutions below

1
On BEST ANSWER

The theorem is false. Take the cube graph ($C_4\square P_2$) and subdivide an edge to get $G$, which satisfies the properties. This gives us an induced $C_5$. When trying to color the graph, we may start with that cycle. Color clockwise such that the 2 edges from the subdivision are colored last (e.g. when the cube is drawn planar like usual and the edge at the bottom is subdivided, start at the vertex in the outer lower left). The first color is arbitrary, say $a$. The next color $\neq a$ is arbitrary too, say $b$. The only possibilities to finish with three colors are $abc$, $acb$, $cab$, $cac$ and $cbc$ (since the third color cannot be $b$ and the fifth cannot be $a$). But none of these can be finished to a 3-edge-coloring, as one can readily verify.

0
On

A simpler proof and more general reason is that the 3-dim cube with one subdivided edge has 9 vertices, so max matching at most 4. Therefore to color all the 13 edges you need at least 13/4 colors, i.e. at least 4.