Spanning trees with many or few colors in edge-colored graphs

• Autorzy: Hajo Broersma , Xueliang Li
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

edge-coloring; spanning tree; matroid (intersection); complexity; NP-complete; NP-hard; polynomial algorithm; (minimum) dominating set

Kategorie tematyczne

• 05B35: Matroids, geometric lattices
• 05C05: Trees
• 05C85: Graph algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1997
• Tom: 17
• Numer: 2
• Strony: 259-269

Daty

wydano

1997

otrzymano

1995-11-23

poprawiono

1997-01-30

Twórcy

autor

Hajo Broersma

• Faculty of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

autor

Xueliang Li

• Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072, P.R. China

Bibliografia

• [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).

Identyfikatory

DOI

10.7151/dmgt.1053