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

Discussiones Mathematicae Graph Theory (1997)

- Volume: 17, Issue: 2, page 259-269
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHajo Broersma, and Xueliang Li. "Spanning trees with many or few colors in edge-colored graphs." Discussiones Mathematicae Graph Theory 17.2 (1997): 259-269. <http://eudml.org/doc/270702>.

@article{HajoBroersma1997,

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.},

author = {Hajo Broersma, Xueliang Li},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge-coloring; spanning tree; matroid (intersection); complexity; NP-complete; NP-hard; polynomial algorithm; (minimum) dominating set; matroids; dominating set},

language = {eng},

number = {2},

pages = {259-269},

title = {Spanning trees with many or few colors in edge-colored graphs},

url = {http://eudml.org/doc/270702},

volume = {17},

year = {1997},

}

TY - JOUR

AU - Hajo Broersma

AU - Xueliang Li

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

JO - Discussiones Mathematicae Graph Theory

PY - 1997

VL - 17

IS - 2

SP - 259

EP - 269

AB - 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.

LA - eng

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

UR - http://eudml.org/doc/270702

ER -

## References

top- [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan-Elsevier, London-New York, 1976). Zbl1226.05083
- [2] M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman, New York, 1979). Zbl0411.68039
- [3] E.L. Lawler, Combinatorial Optimization, Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). Zbl0413.90040
- [4] D.J.A. Welsh, Matroid Theory (Academic Press, London-New York-San Francisco, 1976).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.