Maximum colored trees in edge-colored graphs

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.