ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 17(2) (1997)
Faculty of Applied Mathematics
University of Twente, P.O. Box 217
7500 AE Enschede, The Netherlands
Department of Applied Mathematics
Northwestern Polytechnical University
Xi'an, Shaanxi 710072, P.R. China
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.