Parameterized complexity of Partial Grundy Coloring
Parameterized complexity of Partial Grundy Coloring on general graphs · arXiv:2001.03794
Status solved high confidence
The open problem from arXiv:2001.03794 — whether Partial Grundy Coloring on general graphs is FPT when parameterized by k — was resolved affirmatively. Agrawal, Lokshtanov, Panolan, Saurabh, and Verma (STACS 2025, arXiv:2410.20629) give an FPT algorithm for Partial Grundy Coloring on general graphs, along with an FPT algorithm for Grundy Coloring on K_{i,j}-free graphs, directly answering the question posed in the source paper.
Cited literature (1)
-
Proves that Partial Grundy Coloring on general graphs is FPT when parameterized by k, resolving the open problem posed in arXiv:2001.03794.
Reviewer notes. The resolving paper also gives FPT for Grundy Coloring on K_{i,j}-free graphs, extending the partial results of the source paper. The source paper had shown FPT for Partial Grundy Coloring on K_{t,t}-free graphs; the 2025 paper lifts this to all graphs.
Context
The authors were unable to prove W[1]-hardness for Partial Grundy Coloring because half-graphs cannot serve as color-propagation units (the partial Grundy number is already large on a large half-graph $H_{t,t}$). The class of $H_{t,t}$-free graphs is suggested as a promising intermediate case for understanding the general-graph complexity.
Notes. Stated as an open problem in the 'Limits and further questions' section; no formal numbered theorem environment.
Source paper
Grundy Coloring & friends, Half-Graphs, Bicliques
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora · 2020-01-11
https://arxiv.org/abs/2001.03794
PDF source