Discussiones Mathematicae Graph Theory  17(2) (1997)   259-269
doi: 10.7151/dmgt.1053

## SPANNING TREES WITH MANY OR FEW COLORS IN EDGE-COLORED GRAPHS

 Hajo Broersma Faculty of Applied Mathematics University of Twente, P.O. Box 217 7500 AE Enschede, The Netherlands Xueliang Li Department of Applied Mathematics Northwestern Polytechnical University Xi'an, Shaanxi 710072, P.R. China

## 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.

Keywords: edge-coloring, spanning tree, matroid (intersection), complexity, NP-complete, NP-hard, polynomial algorithm, (minimum) dominating set.

1991 Mathematics Subject Classification: 05C05, 05C85, 05B35.

## References

 [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan-Elsevier, London-New York, 1976). [2] M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman, New York, 1979). [3] E.L. Lawler, Combinatorial Optimization, Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). [4] D.J.A. Welsh, Matroid Theory (Academic Press, London-New York-San Francisco, 1976).