Chromatic index of planar 4-regular graphs

410 Views Asked by At

Planar graphs of max degree 4 are, in general, not necessarily edge-4-colorable. However, what is the situation if the graph is 4-regular, is it edge-4-colorable? I am guessing this is known ... what might be a reference for the answer to this question?

And what is the situation if we require that no two triangles share an edge (although they can share a vertex)?

1

There are 1 best solutions below

15
On

The following graph, taken from this answer (and originally from the paper On the Existence of a Perfect Matching for 4-Regular Graphs Derived from Quadrilateral Meshes by Carbonera and Shepherd), is a counterexample:

enter image description here

This is a planar $4$-regular graph which does not have a perfect matching: deleting the central vertices leaves four odd components. But in any $4$-coloring of the edges, all the color classes would need to be perfect matchings.

If you add the additional constraint that no two triangle faces share an edge, then we can still use essentially the same counterexample. Replace each of the fragments $C_1, C_2, C_3, C_4$ by the following:

enter image description here

This is a $13$-vertex graph in which all vertices except the two highlighted ones have degree $4$, and no two triangles share an edge. Connect the two highlighted vertices to the center $S$ in the same way, and you get another $4$-regular graph with no perfect matching.