@article{0d402f1759994ac295b2c58ae9f388df,
title = "Spanning trees with many or few colors in edge-colored graphs",
abstract = "Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we 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. We 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. We use the minimum dominating set problem to show that the second problem is NP-hard.",
author = "Hajo Broersma and Xueliang Li",
year = "1997",
doi = "10.7151/dmgt.1053",
language = "English",
volume = "17",
pages = "259--270",
journal = "Discussiones mathematicae. Graph theory",
issn = "1234-3099",
publisher = "University of Zielona Gora",
number = "2",
}