10
$\begingroup$

Suppose that we have a 2d-regular graph whose edges are colored such that the edges of each color form a cycle of length 2d. (So if the graph has 2n vertices, then there are n colors.) Is it true that there always is a perfect matching containing one edge of each color?

Remarks. For d=2 there is a simple proof by Zoltan Kiraly who also invented the above formulation of the problem. I even do not know the answer for d=3.

Improve this question
$\endgroup$
5
  • $\begingroup$ And, more generally, can we choose k edges from each cycle in such a way that each vertex is an endpoint of exactly k of the edges? (I've only been able to solve the case d = 1 so far ;) .) $\endgroup$
    – JBL
    May 18, 2010 at 3:23
  • 1
    $\begingroup$ This paper seems slightly relevant: combinatorics.org/Volume_17/Abstracts/v17i1n26.html They prove that if every vertex is incident to edges of $d$ distinct colors then there exists a rainbow matching of size at least $\lfloor d/2\rfloor$ (making no assumptions about the structure of the colored edges, unlike in this question). $\endgroup$
    – JBL
    May 27, 2010 at 13:57
  • $\begingroup$ Thanks! Unfortunately in this case d/2 is already guaranteed by a greedy argument... $\endgroup$
    – domotorp
    May 27, 2010 at 16:20
  • $\begingroup$ What is easy proof for $d=2$? $\endgroup$
    – Fedor Petrov
    Oct 5, 2016 at 19:52
  • 2
    $\begingroup$ @Fedor: Here is his argument. Create a new graph, $H$, by taking the two diagonals of each $C_4$. In $H$ the degree of every vertex is exactly two, thus $H$ is collection of disjoint cycles. Direct each cycle arbitrarily. The two diagonals from each color point to two vertices that are connected with this color in the original graph. Match these. $\endgroup$
    – domotorp
    Oct 5, 2016 at 22:00

2 Answers 2

Reset to default
2
$\begingroup$

This is a little embarrassing, but it turned out that not even a (non-rainbow) matching is guaranteed to exist. The problem was solved on this workshop by a number of people, presented by Tamas Terpai. They raised the same question for bipartite graphs, for which a matching must always exist.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This comment is totally off-topic, but it looks like a great workshop! (I have very fond memories of classes taught by Simonyi and Gyarfas.) $\endgroup$
    – JBL
    Jul 31, 2010 at 18:22
1
$\begingroup$

I like this question, so this non-answer is largely intended just to bump it back to the top in the hope that someone else will make something out of it. Here are some silly comments:

  • The reason we must have an even number of vertices (i.e., why 2n appears in the question instead of n) is because we are looking for a perfect matching.
  • The reason the length of the cycles must be even (i.e., why 2d appears in the question instead of d) is because the degree of each vertex is even: each cycle contributes either 0 or 2 edges to each vertex.
  • The cases $k = 0$ and $k = 2d$ of my suggested generalization are trivial. The case $k = d$ is also easy: from each cycle, take every other edge. It's also clear that if the result holds for $k = a$ then it also holds for $k = 2d - a$.
  • At some point I thought I had come up with a solution for the case $d = 2$, $k = 1$ (i.e., the case domotorp attributes to Z. Kiraly), but I either was mistaken or I have forgotten it. So, I would be interested in seeing even the proof of that case.
  • Assuming we always can make such a choice, is there some more general class of graphs with which we can replace cycles and still have the result be true?
Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Make a bipartite graph where on the lower side you have the vertices of the original graph, on the upper two vertices for each colorclass, each being connected to two opposite vertices of the C_4 of that color. This is a 2-regular bipartite graph now and what we need is a perfect matching. $\endgroup$
    – domotorp
    May 23, 2010 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.