Above-Guarantee Algorithm for Properly Colored Trees
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.11326
curl -X POST /api/v1/records/arxiv/2604.11326/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.11326/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'