On the Grundy and b-Chromatic Numbers of a Graph |
| |
Authors: | Frédéric Havet Leonardo Sampaio |
| |
Affiliation: | 1. Projet Mascotte, I3S (CNRS, UNS) and INRIA, 2004 route des lucioles, BP 93, 06902, Sophia-Antipolis Cedex, France
|
| |
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 vertexes of G. The b-chromatic number of a graph G, denoted by χ b (G), is the largest k such that G has a b-colouring with k colours, that is a colouring in which each colour class contains a b-vertex, a vertex with neighbours in all other colour classes. Trivially χ b (G),Γ(G)≤Δ(G)+1. In this paper, we show that deciding if Γ(G)≤Δ(G) is NP-complete even for a bipartite graph G. We then show that deciding if Γ(G)≥|V(G)|?k or if χ b (G)≥|V(G)|?k are fixed parameter tractable problems with respect to the parameter k. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|