Discussiones Mathematicae Graph Theory 17(2) (1997)
259-269
doi: 10.7151/dmgt.1053
Hajo Broersma Faculty of Applied Mathematics |
Xueliang Li Department of Applied Mathematics |
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.
[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). |