Above-Guarantee Algorithm for Properly Colored Spanning Trees

Krist\'of B\'erczi; Yuhang Bai

arxiv: 2604.11326 · v1 · submitted 2026-04-13 · 💻 cs.DS · math.CO

Above-Guarantee Algorithm for Properly Colored Spanning Trees

Yuhang Bai , Krist\'of B\'erczi This is my paper

Pith reviewed 2026-05-10 16:14 UTC · model grok-4.3

classification 💻 cs.DS math.CO

keywords properly colored spanning treeedge-colored graphsminimum color degreeabove-guarantee algorithmpolynomial-time algorithmsspanning treesgraph algorithms

0 comments

The pith

A polynomial-time algorithm 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.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper focuses on finding properly colored spanning trees in edge-colored graphs, a task that is NP-hard without additional conditions. It presents a polynomial-time algorithm that finds a properly colored tree of size at least the minimum of the number of vertices or twice the minimum color degree plus one. This builds on the known existence of trees of size 2δ^c by providing an efficient way to construct one that is one vertex larger. The minimum color degree δ^c(G) is the smallest number of different colors touching any vertex in the graph. This is useful because it offers a practical method to build larger properly colored trees in polynomial time when they are guaranteed to exist.

Core claim

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.

What carries the argument

The polynomial-time above-guarantee algorithm that achieves a properly colored tree of order 2δ^c(G)+1 using the minimum color degree condition.

If this is right

The algorithm allows efficient construction of properly colored trees that are larger than those guaranteed by non-algorithmic results.
The NP-hardness of the general problem does not prevent polynomial-time solutions for this improved size guarantee.
The result requires the graph to be connected but works for any edge-coloring satisfying the condition.
It turns an existence theorem into a constructive procedure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This +1 improvement might allow for better approximations to the maximum size properly colored tree problem.
Similar algorithmic techniques could be applied to other problems in edge-colored graphs such as finding long properly colored paths.
The approach highlights how small improvements in guarantee can make algorithmic versions tractable.

Load-bearing premise

The graph is connected and a properly colored tree of size at least min{|V(G)|, 2δ^c(G)+1} exists.

What would settle it

A connected edge-colored graph G for which a properly colored tree of order min{|V(G)|, 2δ^c(G)+1} exists, but the algorithm does not find one in polynomial time.

Figures

Figures reproduced from arXiv: 2604.11326 by Krist\'of B\'erczi, Yuhang Bai.

**Figure 2.** Figure 2: Illustration of Case G¯′ ∈ G6 of the proof of Theorem 4.11. Take G¯′ ∼= G6 3,1 . Add e0 = u1u4. The conflict edges are E• = {v1u1, v1u4}, and the thick edges and e0 form the rainbow tree on 2δ c + 1 = 7 vertices. Claim 4.14. Let F be either G′ or G′′. Let H be a subgraph of F, and let H¯ be the corresponding subgraph of F¯ with E(H¯ ) = E(H). Then H is properly colored in F if and only if H¯ is rainbow in … view at source ↗

**Figure 3.** Figure 3: Illustration of Case G¯′ ∈ G4 of the proof of Theorem 4.11. Take G¯′ ∼= G4 2,1 . and y = um+1. Choose m − 1 distinct vertices u2, . . . , um ∈ I \ {x, y}. By the above argument, for each i with 2 ≤ i ≤ m, the edge viui is in G¯′′ . Note that Q0 is a star centered at either x or y. Since d c G′′ (x) = m ≥ 2, there exists an edge xvs ∈ E(G′′) whose original color is distinct from that of e0. By relabeling th… view at source ↗

**Figure 4.** Figure 4: Illustration of Case G¯′ ∈ G1 of the proof of Theorem 4.11. Finally, let T = T0 + e0. Since y /∈ V (T0) and E(T0) ∩ E(Q0) = ∅, the graph T is a rainbow tree of order 2δ c (G¯′′) + 1 in G¯′′; see [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a poly-time algorithm for a properly colored tree one larger than the known existential bound of 2δ^c, but the claim looks like it would decide an NP-hard spanning-tree case in the high-δ^c regime without explaining how.

read the letter

The punchline is that this turns a non-constructive existence result into a polynomial-time construction that gets one extra vertex, but only when the larger tree exists. That is the actual advance: previous work had the 2δ^c guarantee, and here they make an algorithmic version that beats it by one under the same minimum color-degree condition. The abstract is clear on the claim and the input assumptions (connected graph, existence given), so the contribution sits squarely in the above-guarantee algorithmic literature for edge-colored graphs. Credit for making the improvement constructive rather than leaving it existential. The technique itself is not described in the abstract, but the result is internally consistent with what is stated. The soft spot is the complexity interaction the stress-test flags. Finding a properly colored spanning tree is NP-hard in general. When δ^c is high enough that 2δ^c +1 reaches n, the algorithm is required to output a spanning tree whenever one exists. A correct poly-time procedure for that would decide existence in the boundary case, which contradicts the hardness unless hardness instances are confined to lower color degrees. The abstract does not address this or restrict the input class, so the claim needs either a proof that the algorithm stays polynomial without solving the hard problem or an explicit statement that the +1 guarantee never forces a spanning-tree decision. Minor gaps in the write-up could be fixed, but this one is load-bearing for the main result. The paper is aimed at researchers who work on parameterized and above-guarantee algorithms for graph problems with color constraints. A reader already following that line would find the +1 improvement worth seeing, even if the details need checking. It is worth sending to peer review so the authors can clarify the complexity point and let referees verify the color-handling steps in the proof.

Referee Report

1 major / 0 minor

Summary. The manuscript presents a polynomial-time algorithm that constructs a properly colored tree of order at least min{|V(G)|, 2δ^c(G)+1} in any connected edge-colored graph G, provided that such a tree exists. This is framed as an above-guarantee algorithmic result relative to the known existential bound of 2δ^c(G).

Significance. If correct, the result would give a constructive way to obtain properly colored trees one vertex larger than the existential guarantee, which could have implications for approximation or parameterized algorithms in edge-colored graph problems. The paper correctly identifies the NP-hardness of the spanning tree variant in general.

major comments (1)

[Abstract] The claimed algorithm is polynomial-time and, in regimes where 2δ^c(G)+1 = |V(G)| (e.g., when δ^c(G) = ⌈(|V|-1)/2⌉ for odd |V|), constructs a properly colored spanning tree whenever one exists. Since the existence decision problem is NP-hard (as noted in the abstract), running the algorithm and checking whether the output tree spans all vertices would decide the NP-hard problem in polynomial time, leading to a contradiction. The manuscript does not restrict the hardness to instances with smaller color degree, making this a load-bearing issue for the central algorithmic claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a critical inconsistency between the stated algorithmic result and the known NP-hardness of the Properly Colored Spanning Tree problem. We address the concern directly below and indicate the revisions that will be made.

read point-by-point responses

Referee: [Abstract] The claimed algorithm is polynomial-time and, in regimes where 2δ^c(G)+1 = |V(G)| (e.g., when δ^c(G) = ⌈(|V|-1)/2⌉ for odd |V|), constructs a properly colored spanning tree whenever one exists. Since the existence decision problem is NP-hard (as noted in the abstract), running the algorithm and checking whether the output tree spans all vertices would decide the NP-hard problem in polynomial time, leading to a contradiction. The manuscript does not restrict the hardness to instances with smaller color degree, making this a load-bearing issue for the central algorithmic claim.

Authors: We agree that the current formulation of the main result creates a contradiction with NP-hardness. The manuscript states that a polynomial-time algorithm constructs a properly colored tree of order at least min{|V(G)|, 2δ^c(G)+1} whenever such a tree exists, without restricting the claim to instances where 2δ^c(G)+1 < |V(G)| or to regimes where existence is polynomial-time decidable. Because the NP-hardness of deciding the existence of a properly colored spanning tree is stated without a color-degree restriction, the referee's observation is correct: in the regime δ^c(G) ≥ ⌈(|V|-1)/2⌉ the algorithm would decide an NP-hard problem. We will therefore revise the abstract, the introduction, and the statement of the main theorem to remove the unqualified “whenever such a tree exists” phrasing for the +1 guarantee. The revised claim will be that the algorithm always produces, in polynomial time, a properly colored tree of order at least 2δ^c(G), and that an additional linear-time post-processing step can sometimes enlarge it by one vertex; we will explicitly note that the +1 enlargement is not guaranteed to succeed in polynomial time when the target size equals |V(G)|. We will also add a remark clarifying that the known NP-hardness instances can be chosen with arbitrarily large minimum color degree, so no implicit restriction saves the original claim. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic construction independent of existential bound

full rationale

The paper cites a known existential result that every connected edge-colored graph contains a properly colored tree of order at least min{|V(G)|, 2δ^c(G)} and contributes a separate polynomial-time algorithm to construct one of order at least min{|V(G)|, 2δ^c(G)+1} whenever such a tree exists. No step reduces by definition, by fitting a parameter then relabeling it as a prediction, or by a load-bearing self-citation whose justification collapses into the present work. The constructive algorithm is an independent addition rather than a renaming or self-referential rederivation of the input bound, making the derivation chain self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard graph-theoretic assumptions such as connectivity and the definition of proper edge coloring. No free parameters are introduced, and no new entities are postulated. The algorithm is presented as a direct constructive procedure without additional fitted constants.

axioms (2)

domain assumption The input graph is undirected, connected, and edge-colored.
Stated in the abstract as the setting for the problem and the guarantee.
domain assumption A properly colored spanning tree of the claimed size exists in the input graph.
The algorithm is conditional on this existence; the paper does not claim to decide existence.

pith-pipeline@v0.9.0 · 5451 in / 1465 out tokens · 25501 ms · 2026-05-10T16:14:22.168309+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Y. Bai, K. B´ erczi, G. Cs´ aji, and T. Schwarcz. Approximating maximum-size properly colored forests. European Journal of Combinatorics, 132:104269, 2026

work page 2026
[2]

Y. Bai, K. B´ erczi, and J. K. Siemelink. Approximating maximum properly colored forests via degree bounded independent sets.arXiv preprint arXiv:2511.18263, 2025

work page arXiv 2025
[3]

Borozan, W

V. Borozan, W. Fernandez de La Vega, Y. Manoussakis, C. Martinhon, R. Muthu, H. P. Pham, and R. Saad. Maximum colored trees in edge-colored graphs.European Journal of Combinatorics, 80:296– 310, 2019

work page 2019
[4]

Cheng, M

Y. Cheng, M. Kano, and G. Wang. Properly colored spanning trees in edge-colored graphs.Discrete Mathematics, 343(1):111629, 2020

work page 2020
[5]

G. A. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

work page 1952
[6]

J. Edmonds. Submodular functions, matroids, and certain polyhedra. InCombinatorial Structures and Their Applications, pages 69–87. Gorden and Breach, New York, 1970. (Also inCombinatorial Optimization — Eureka, You Shrink!, pages 11–26, Springer, Berlin, Heidelberg, 2003.)

work page 1970
[7]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Algorithmic extensions of Dirac’s theorem. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 406–416. SIAM, 2022

work page 2022
[8]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Approximating long cycle above Dirac’s guarantee.Algorithmica, 86(8):2676–2713, 2024. 17

work page 2024
[9]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Longest cycle above Erd˝ os–Gallai bound. SIAM Journal on Discrete Mathematics, 38(4):2721–2749, 2024

work page 2024
[10]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Tree containment above minimum degree is FPT.ACM Transactions on Algorithms, 22(1):1–44, 2025

work page 2025
[11]

Frank.Connections in Combinatorial Optimization, volume 38 ofOxford Lecture Series in Mathe- matics and its Applications

A. Frank.Connections in Combinatorial Optimization, volume 38 ofOxford Lecture Series in Mathe- matics and its Applications. Oxford University Press, Oxford, 2011

work page 2011
[12]

Gutin and M

G. Gutin and M. Mnich. A survey on graph problems parameterized above and below guaranteed values. Computer Science Review, 58:100795, 2025

work page 2025
[13]

J. Hu, H. Li, and S.-i. Maezawa. Maximum properly colored trees in edge-colored graphs.Journal of Combinatorial Optimization, 44(1):154–171, 2022

work page 2022
[14]

Kano, S.-i

M. Kano, S.-i. Maezawa, K. Ota, M. Tsugaki, and T. Yashima. Color degree sum conditions for properly colored spanning trees in edge-colored graphs.Discrete Mathematics, 343(11):112042, 2020

work page 2020
[15]

Kano and M

M. Kano and M. Tsugaki. Rainbow and properly colored spanning trees in edge-colored bipartite graphs. Graphs and Combinatorics, 37(5):1913–1921, 2021

work page 1913
[16]

Oxley.Matroid Theory, volume 21 ofOxford Graduate Texts in Mathematics

J. Oxley.Matroid Theory, volume 21 ofOxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011

work page 2011
[17]

K. Suzuki. A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph.Graphs and Combinatorics, 22(2):261–269, 2006. A Remaining cases in the proof of Theorem 4.1 In this appendix we continue the proof of Theorem 4.1 in the remaining casesm= 2 andm= 1 under the standing assumptions |V(T)|= 2δ c(G) andV(T)̸=V(G). W...

work page 2006

[1] [1]

Y. Bai, K. B´ erczi, G. Cs´ aji, and T. Schwarcz. Approximating maximum-size properly colored forests. European Journal of Combinatorics, 132:104269, 2026

work page 2026

[2] [2]

Y. Bai, K. B´ erczi, and J. K. Siemelink. Approximating maximum properly colored forests via degree bounded independent sets.arXiv preprint arXiv:2511.18263, 2025

work page arXiv 2025

[3] [3]

Borozan, W

V. Borozan, W. Fernandez de La Vega, Y. Manoussakis, C. Martinhon, R. Muthu, H. P. Pham, and R. Saad. Maximum colored trees in edge-colored graphs.European Journal of Combinatorics, 80:296– 310, 2019

work page 2019

[4] [4]

Cheng, M

Y. Cheng, M. Kano, and G. Wang. Properly colored spanning trees in edge-colored graphs.Discrete Mathematics, 343(1):111629, 2020

work page 2020

[5] [5]

G. A. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

work page 1952

[6] [6]

J. Edmonds. Submodular functions, matroids, and certain polyhedra. InCombinatorial Structures and Their Applications, pages 69–87. Gorden and Breach, New York, 1970. (Also inCombinatorial Optimization — Eureka, You Shrink!, pages 11–26, Springer, Berlin, Heidelberg, 2003.)

work page 1970

[7] [7]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Algorithmic extensions of Dirac’s theorem. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 406–416. SIAM, 2022

work page 2022

[8] [8]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Approximating long cycle above Dirac’s guarantee.Algorithmica, 86(8):2676–2713, 2024. 17

work page 2024

[9] [9]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Longest cycle above Erd˝ os–Gallai bound. SIAM Journal on Discrete Mathematics, 38(4):2721–2749, 2024

work page 2024

[10] [10]

F. V. Fomin, P. A. Golovach, D. Sagunov, and K. Simonov. Tree containment above minimum degree is FPT.ACM Transactions on Algorithms, 22(1):1–44, 2025

work page 2025

[11] [11]

Frank.Connections in Combinatorial Optimization, volume 38 ofOxford Lecture Series in Mathe- matics and its Applications

A. Frank.Connections in Combinatorial Optimization, volume 38 ofOxford Lecture Series in Mathe- matics and its Applications. Oxford University Press, Oxford, 2011

work page 2011

[12] [12]

Gutin and M

G. Gutin and M. Mnich. A survey on graph problems parameterized above and below guaranteed values. Computer Science Review, 58:100795, 2025

work page 2025

[13] [13]

J. Hu, H. Li, and S.-i. Maezawa. Maximum properly colored trees in edge-colored graphs.Journal of Combinatorial Optimization, 44(1):154–171, 2022

work page 2022

[14] [14]

Kano, S.-i

M. Kano, S.-i. Maezawa, K. Ota, M. Tsugaki, and T. Yashima. Color degree sum conditions for properly colored spanning trees in edge-colored graphs.Discrete Mathematics, 343(11):112042, 2020

work page 2020

[15] [15]

Kano and M

M. Kano and M. Tsugaki. Rainbow and properly colored spanning trees in edge-colored bipartite graphs. Graphs and Combinatorics, 37(5):1913–1921, 2021

work page 1913

[16] [16]

Oxley.Matroid Theory, volume 21 ofOxford Graduate Texts in Mathematics

J. Oxley.Matroid Theory, volume 21 ofOxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011

work page 2011

[17] [17]

K. Suzuki. A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph.Graphs and Combinatorics, 22(2):261–269, 2006. A Remaining cases in the proof of Theorem 4.1 In this appendix we continue the proof of Theorem 4.1 in the remaining casesm= 2 andm= 1 under the standing assumptions |V(T)|= 2δ c(G) andV(T)̸=V(G). W...

work page 2006