{"id":"arxiv/2604.11326","url":"https://arxiv.org/abs/2604.11326","tags":["cs.DS","math.CO"],"score":0,"title":"Above-Guarantee Algorithm for Properly Colored Trees","domain":"cs.DS","source":"arxiv","authors":["Yuhang Bai","Kristóf Bérczi"],"reviews":0,"subject":"cs.DS","summary":"In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a spanning tree in which any two adjacent edges have distinct colors. Since finding such a tree is NP-hard in general, previous work often relied on minimum color degree conditions to guarantee the existence of properly colored spanning trees. While it is known that every connected edge-colored graph $G$ contains a properly colored tree of order at least $\\min\\{|V(G)|, 2δ^c(G)\\}$, where $δ^c(G)$ denotes the minimum number of colors incident to a vertex, we study the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-13","reactions":{}}