Complexity of Grundy Coloring and Its Variants

Bonnet, É., Foucaud, F., Kim, E. J., & Sikora, F. (2018). Complexity of Grundy Coloring and Its Variants. Discrete Applied Mathematics, 99-114.

Type

Journal article

Intellectual base

Primary research

Year

2018

DOI

10.1016/j.dam.2017.12.022

Link

https://doi.org/10.1016/j.dam.2017.12.022

Cited by

1 citation across 1 artifact.

Domain-specific

• Grundy Number
  • … shows that deciding whether \(\Gamma(G)\geq k\) is polynomial for fixed \(k\), while general computation is NP-complete, and defines well-colored graphs by \(\Gamma(G)=\chi(G)\). Later complexity work distinguishes Grundy Coloring from weak and connected variants and maps fixed-parameter behavior across graph classes.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:1f94e57456b0 · see in the full table