Let $G$ be a $3$-connected cubic graph.
Does $G$ have a matching $M$ such that the $4$-regular multigraph $H$ resulting from contracting the matching $M$ is $4$-edge-colorable?
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
The Petersen graph is a counterexample.
$\begingroup$
$\endgroup$
4
Two people answered that the Petersen graph is a counterexample. They are correct, but it is more interesting to note that any cubic graph with $4k+2$ vertices is a counterexample. The contracted graph has $2k+1$ vertices an $4k+2$ edges. Each edge colour can appear on at most $k$ edges so at least 5 colors are needed.
For $4k$ vertices: Take any simple quartic graph with $2k$ vertices and stretch out each vertex into a new edge joining two vertices of degree 3. This is the reverse of the operation given. So every simple quartic graph wit $4k$ vertices can be produced by contracting a perfect matching in a cubic graph. Is every quartic graph 4-edge-colourable? I don't think so; actually I think it is NP-hard.
answered Oct 15, 2016 at 8:38
-
$\begingroup$ So is the OP's question true for cubic graphs of order $4k$? $\endgroup$ Oct 15, 2016 at 10:07
-
-
1$\begingroup$ That's a very nice argument, for graphs with $4k+2$ vertices! However, edge $4$-colorability of $4$-regular graphs is not necessary for a positive answer to the OP's question: different matchings can produce different $4$-regular graphs. In fact, the disjoint union of two $K_5$ is not edge $4$-colorable. A more "fair" counterexample: $K_5$ without an edge is not edge $4$-colorable, so we can take two copies of it and pair the degree $3$ vertices of one copy to those of the other copy. What graphs can be obtained by "stretching out" all vertices and contracting along a matching? $\endgroup$ Oct 17, 2016 at 5:07
-
$\begingroup$
$\endgroup$
I don't think you can find such a matching in the Petersen graph.
The graph, post-contraction, is just the complete graph on 5 vertices, as there can be no double edges.
answered Oct 15, 2016 at 5:15