Geodesic
Spanning trees with many or few colors in edge-colored graphs
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 2, pp. 259-269 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_1997_17_2_a4,
     author = {Broersma, Hajo and Li, Xueliang},
     title = {Spanning trees with many or few colors in edge-colored graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {259--269},
     year = {1997},
     volume = {17},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a4/}
}
TY  - JOUR
AU  - Broersma, Hajo
AU  - Li, Xueliang
TI  - Spanning trees with many or few colors in edge-colored graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 259
EP  - 269
VL  - 17
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a4/
LA  - en
ID  - DMGT_1997_17_2_a4
ER  - 
%0 Journal Article
%A Broersma, Hajo
%A Li, Xueliang
%T Spanning trees with many or few colors in edge-colored graphs
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 259-269
%V 17
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a4/
%G en
%F DMGT_1997_17_2_a4
Broersma, Hajo; Li, Xueliang. Spanning trees with many or few colors in edge-colored graphs. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 2, pp. 259-269. http://geodesic.mathdoc.fr/item/DMGT_1997_17_2_a4/

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