On the Grundy number of a graph

Frédéric Havet 1 Leonardo Sampaio 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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$.
Type de document :
Communication dans un congrès
Fifth International Symposium on Parameterized and Exact Computation (IPEC 2010), Dec 2010, Chennai, India. Springer, 6478, pp.170--179, 2010, Parameterized and Exact Computation. <10.1007/978-3-642-17493-3>
Liste complète des métadonnées


https://hal.inria.fr/inria-00532906
Contributeur : Leonardo Sampaio <>
Soumis le : vendredi 5 novembre 2010 - 16:03:35
Dernière modification le : jeudi 16 décembre 2010 - 18:11:31
Document(s) archivé(s) le : dimanche 6 février 2011 - 02:34:40

Fichier

FPT-dual-greedy.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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. Springer, 6478, pp.170--179, 2010, Parameterized and Exact Computation. <10.1007/978-3-642-17493-3>. <inria-00532906>

Partager

Métriques

Consultations de
la notice

162

Téléchargements du document

112