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
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00905927
Contributor : Frederic Havet <>
Submitted on : Sunday, October 23, 2016 - 4:15:45 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

File

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

Identifiers

  • 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⟩

Share

Metrics

Record views

507

Files downloads

184