Skip to Main content Skip to Navigation
New interface
Journal articles

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 , Laboratoire I3S - 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Sunday, October 23, 2016 - 4:15:45 PM
Last modification on : Thursday, August 4, 2022 - 4:58:24 PM


Files produced by the author(s)


  • HAL Id : hal-00905927, version 1



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



Record views


Files downloads