Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where $V_k=\{v_1,\ldots,v_k\}$ is a subset of the vertices. Is it always possible to find a family of vertex disjoint paths such that

  1. for $i=1,.., k$ every $v_i$ is contained in a path,
  2. each path consists of vertices only from $V_k$ except for exactly one of its endpoints which must be outside of $V_k$,
  3. in each path the red and blue edges are alternating?

The claim is true if $k$ is small (<6). It is also true if the red graph and the blue graph are the same. This question was brought to my attention by a few friends who could use it in one of their papers in preparation.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.