1
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

The Petersen graph is a counterexample.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So is the OP's question true for cubic graphs of order $4k$? $\endgroup$
    – Gordon Royle
    Commented Oct 15, 2016 at 10:07
  • $\begingroup$ @Gordon: See my additions. $\endgroup$
    – Brendan McKay
    Commented Oct 17, 2016 at 1:35
  • 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$
    – Ivan Izmestiev
    Commented Oct 17, 2016 at 5:07
  • $\begingroup$ @Ivan : Yes you are right. $\endgroup$
    – Brendan McKay
    Commented Oct 17, 2016 at 22:10
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .