Grundy Coloring FPT on K_{t,t}-free graphs

FPT on $K_{t,t}$-free graphs for Grundy Coloring · arXiv:2001.03794

arXiv Problem medium confidence— first stated 2020-01-11

Authors: Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora

Status solved high confidence

The open question of whether \textsc{Grundy Coloring} is FPT on $K_{t,t}$-free graphs parameterized by $k$ was resolved affirmatively by Agrawal, Lokshtanov, Panolan, Saurabh, and Verma (arXiv:2410.20629, STACS 2025), which provides an FPT algorithm for Grundy Coloring on $K_{i,j}$-free graphs (subsuming $K_{t,t}$-free) parameterized by $k$, alongside an FPT algorithm for Partial Grundy Coloring on general graphs.

Cited literature (1)

proof Parameterized Saga of First-Fit and Last-Fit Coloring (2024)

Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Shaily Verma · STACS 2025 (arXiv preprint 2410.20629) · arXiv:2410.20629

Proves an FPT algorithm for Grundy Coloring on $K_{i,j}$-free graphs parameterized by $k$, directly resolving the open question from arXiv:2001.03794.

Reviewer notes. arXiv:2410.20629 (Agrawal et al., STACS 2025) settles this problem by proving FPT for Grundy Coloring on K_{i,j}-free graphs, which subsumes K_{t,t}-free graphs. The URL was verified via WebFetch and the abstract explicitly confirms this result.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Does \textsc{Grundy Coloring} admit a fixed-parameter tractable algorithm on $K_{t,t}$-free graphs when parameterized by $k$?

Context

The paper establishes FPT algorithms for b-Chromatic Core and Partial Grundy Coloring on $K_{t,t}$-free graphs (parameterized by $k+t$), but the analogous question for Grundy Coloring on $K_{t,t}$-free graphs is explicitly left unsettled.

Notes. Stated explicitly as unsettled 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