Above-Guarantee Algorithm for Properly Colored Spanning Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913025949171712 |
|---|---|
| author | Bai, Yuhang Bérczi, Kristóf |
| author_facet | Bai, Yuhang Bérczi, Kristóf |
| contents | 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 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δ^c(G)+1\}$ in a connected edge-colored graph $G$, whenever such a tree exists. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11326 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Above-Guarantee Algorithm for Properly Colored Spanning Trees Bai, Yuhang Bérczi, Kristóf Data Structures and Algorithms Combinatorics 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 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δ^c(G)+1\}$ in a connected edge-colored graph $G$, whenever such a tree exists. |
| title | Above-Guarantee Algorithm for Properly Colored Spanning Trees |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2604.11326 |