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

Hajo Broersma | Zendy; Xue Liang Li | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Hajo Broersma,

Xue Liang Li

Publication year - 1997

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1053

Subject(s) - colored , mathematics , combinatorics , spanning tree , enhanced data rates for gsm evolution , edge coloring , graph , computer science , artificial intelligence , line graph , sociology , graph power , anthropology

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research