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

Haitze J. Broersma, Xueliang Li, Xueliang Li

Research output: Contribution to journalArticleAcademicpeer-review

207 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)259-270
Number of pages12
JournalDiscussiones mathematicae. Graph theory
Volume17
Issue number2
DOIs
Publication statusPublished - 1997

    Fingerprint

Keywords

  • IR-96370
  • METIS-140799

Cite this