most recent 30 from http://mathoverflow.net 2013-06-19T10:12:02Z http://mathoverflow.net/feeds/question/25807 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25807/finding-two-rainbow-spanning-trees Dave Pritchard 2010-05-24T21:00:03Z 2010-06-18T16:11:27Z

<p>Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.</p> <p>Is the following problem NP-complete? Determine whether there are two edge-disjoint spanning trees, such that in each individual tree, no colour appears twice.</p> <p>I am curious because the variant "determine whether there are two edge-disjoint spanning trees, such that in the <strong>union</strong> of the trees, no colour appears twice" is solvable in polynomial time, for example using matroid theory.</p>

http://mathoverflow.net/questions/25807/finding-two-rainbow-spanning-trees/25871#25871 domotorp 2010-05-25T13:32:45Z 2010-06-18T16:11:27Z

<p>Here are some nice lemmas that you can use: <a href="http://www.cs.elte.hu/egres/qp/egresqp-10-04.pdf" rel="nofollow">http://www.cs.elte.hu/egres/qp/egresqp-10-04.pdf</a></p> <p>Dave pointed out my mistake, the subgraphs of spanning trees do not have to be trees. So I have no clue about the answer.</p> <p>Espacially Problem 4 (or 10) seems promising. Take the graph from their construction such that all of its edges have a different color, suppose it has e edges. Then if we allow multigraphs, adding every edge with multiplicity 2n-2-e, all of a different color but same for each edge (thus in total we have 2n-2 colors) shows that your question solvable in P is NP-hard for multigraphs. Am I right? I would guess that with some further tricks you can make a simple graph from this for the variant you asked.</p>