DMGT

Discussiones Mathematicae Graph Theory 17(2) (1997) 259-269
DOI: https://doi.org/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).