On the Grundy number of a graph - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Lecture Notes in Computer Science Année : 2010

On the Grundy number of a graph

Résumé

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$.
Fichier principal
Vignette du fichier
FPT-dual-greedy.pdf (144.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00532906 , version 1 (05-11-2010)

Identifiants

Citer

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⟩
200 Consultations
149 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More