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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1053,
author = {Hajo Broersma and Xueliang Li},
title = {Spanning trees with many or few colors in edge-colored graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {17},
year = {1997},
pages = {259-269},
zbl = {0923.05018},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1053}
}
Hajo Broersma; Xueliang Li. Spanning trees with many or few colors in edge-colored graphs. Discussiones Mathematicae Graph Theory, Tome 17 (1997) pp. 259-269. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1053/
[000] [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan-Elsevier, London-New York, 1976). | Zbl 1226.05083
[001] [2] M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman, New York, 1979). | Zbl 0411.68039
[002] [3] E.L. Lawler, Combinatorial Optimization, Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). | Zbl 0413.90040
[003] [4] D.J.A. Welsh, Matroid Theory (Academic Press, London-New York-San Francisco, 1976).