Publication: Maximum colored trees in edge-colored graphs
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Research Projects
Organizational Units
Journal Issue
Abstract
We consider maximum properly edge-colored�trees�in edge-colored graphs. We also consider the problem where, given a vertex�, determine whether the graph has a spanning tree rooted at�, such that all root-to-leaf paths are properly�colored. We consider these problems from graph-theoretic as well as algorithmic viewpoints. We prove their optimization versions to be NP-hard in general and provide algorithms for graphs without properly edge-colored cycles. We also derive some nonapproximability bounds. A study of the trends random graphs display with regard to the presence of properly edge-colored spanning trees is presented.
Description
Keywords
Citation
Valentin Borozan, W Fernandez de La Vega, Yannis Manoussakis, C Martinhon, Muthu, Rahul, Hong Phong Pham and Rachid Saad"Maximum colored trees in edge-colored graphs," European Journal of Combinatorics, vol. 80, Elsevier, pp. 296-310, Aug. 2019 doi: 10.1016/j.ejc.2018.02.027