Abstract: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\delta^c(G)\}$, where $\delta^c(G)$ denotes the minimum number of colors incident to a vertex, we study the algorithmic above-guarantee problem for properly colored trees. We provide a polynomial-time algorithm that constructs a properly colored tree of order at least $\min\{|V(G)|, 2\delta^c(G)+1\}$ in a connected edge-colored graph $G$, whenever such a tree exists.
From: Kristóf Bérczi [view email]
[v1]
Mon, 13 Apr 2026 11:29:42 UTC (274 KB)
[v2]
Mon, 29 Jun 2026 07:40:59 UTC (351 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。