FPT on H_{t,t}-free graphs for Grundy Coloring

Status open high confidence

The question of whether Grundy Coloring and b-Chromatic Core are FPT on $H_{t,t}$-free graphs (parameterized by $k$) was explicitly left open in the source paper and remains unresolved as of 2026. A STACS 2025 paper (arXiv:2410.20629) establishes FPT for Grundy Coloring on $K_{i,j}$-free graphs and for Partial Grundy Coloring on general graphs, advancing the broader parameterized landscape for greedy coloring problems, but does not directly address the $H_{t,t}$-free case. No paper resolving or disproving the conjecture was found.

Cited literature (1)

• partial Parameterized Saga of First-Fit and Last-Fit Coloring (2025)
  not confirmed in fetch · STACS 2025 (LIPIcs, vol. 327) · arXiv:2410.20629 · doi:10.4230/LIPIcs.STACS.2025.5

  Proves FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on $K_{i,j}$-free graphs, the closest known advance to the $H_{t,t}$-free question, but the $H_{t,t}$-free case is not settled.

Reviewer notes. The source paper already achieves FPT on $K_{t,t}$-free graphs for b-Chromatic Core and Partial Grundy Coloring; the open question is whether excluding $H_{t,t}$ (the half-graph, which drives the W[1]-hardness construction) suffices to give FPT for the full Grundy Coloring and b-Chromatic Core. The key combinatorial lemma for $K_{t,t}$-free graphs was shown to collapse on $H_{t,t}$-free graphs. The STACS 2025 result on $K_{i,j}$-free graphs is the closest known related progress but does not directly resolve the conjecture. No follow-up resolving or disproving the $H_{t,t}$-free case was found in the indexed literature.

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