Red-blue alternating paths - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:13:45Z http://mathoverflow.net/feeds/question/12408 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12408/red-blue-alternating-paths Red-blue alternating paths domotorp 2010-01-20T12:32:13Z 2010-01-20T12:45:16Z <p>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</p> <ol> <li>for \$i=1,.., k\$ every \$v_i\$ is contained in a path,</li> <li>each path consists of vertices only from \$V_k\$ except for exactly one of its endpoints which must be outside of \$V_k\$,</li> <li>in each path the red and blue edges are alternating?</li> </ol> <p>The claim is true if \$k\$ is small (&lt;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.</p>