Spanning Trees with Many or Few Colors in Edge-Colored Graphs

摘要

Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, theauthors consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. The authors show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. The authors use the minimum dominating set problem to show that the second problem is NP-hard.