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

Hajo Broersma; Xueliang Li

Discussiones Mathematicae Graph Theory (1997)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.