HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

On the Grundy number of a graph

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The Grundy number of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a greedy $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. Trivially $\Gamma(G)\leq \Delta(G)+1$. In this paper, we show that deciding if $\Gamma(G)\leq \Delta(G)$ is NP-complete. We then show that deciding if $\Gamma(G)\geq |V(G)|-k$ is fixed parameter tractable with respect to the parameter $k$.
Document type :
Conference papers

Cited literature [14 references]

https://hal.inria.fr/inria-00532906
Contributor : Leonardo Sampaio Connect in order to contact the contributor
Submitted on : Friday, November 5, 2010 - 4:03:35 PM
Last modification on : Friday, February 4, 2022 - 3:19:53 AM
Long-term archiving on: : Sunday, February 6, 2011 - 2:34:40 AM

File

FPT-dual-greedy.pdf
Files produced by the author(s)

Citation

Frédéric Havet, Leonardo Sampaio. On the Grundy number of a graph. Fifth International Symposium on Parameterized and Exact Computation (IPEC 2010), Dec 2010, Chennai, India. pp.170--179, ⟨10.1007/978-3-642-17493-3⟩. ⟨inria-00532906⟩

Record views