On the Grundy and b-chromatic numbers of a graph

Frédéric Havet 1 Leonardo Sampaio 1
1 COATI - Combinatorics, Optimization and Algorithms 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 Γ(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 Γ (G) ≤ ∆(G) + 1. In this paper, we show that deciding if Γ (G) ≤ ∆(G) is NP-complete. We then show that deciding if Γ (G) ≥ |V (G)| − k is fixed parameter tractable with respect to the parameter k.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2013, 65 (4), pp.885-899
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00905927
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:15:45
Dernière modification le : lundi 12 décembre 2016 - 11:35:15

Fichier

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

Identifiants

  • HAL Id : hal-00905927, version 1

Collections

Citation

Frédéric Havet, Leonardo Sampaio. On the Grundy and b-chromatic numbers of a graph. Algorithmica, Springer Verlag, 2013, 65 (4), pp.885-899. 〈hal-00905927〉

Partager

Métriques

Consultations de
la notice

239

Téléchargements du document

91