News

Packing rainbow spanning trees

While the problem of packing common bases in the intersection of two matroids was shown to be hard in general by Bérczi and Schwarcz, identifying tractable special cases remained an interesting problem. In particular, when one of the matroids is a partition matroid and the other is the graphic matroid of an undirected graph, then we get back the problem of packing rainbow spanning trees. In our recent paper On the complexity of packing rainbow spanning trees, we show that it is NP-complete to decide whether an edge-colored graph can be partitioned into disjoint rainbow spanning trees. Our complexity result holds even for the very special case when the graph is the union of two spanning trees and each color class contains exactly two edges.