inria-00639008, version 1
On the Grundy number of graphs with few P4's
Discrete Applied Mathematics 160, 18 (2012) 2514-2522
Résumé : The Grundy number of a graph G is the largest number of colors used by any execution of the greedy algorithm to color G. The problem of determining the Grundy number of G is polynomial if G is a P4-free graph and NP-hard if G is a P5-free graph. In this article, we define a new class of graphs, the fat-extended P4-laden graphs, and we show a polynomial time algorithm to determine the Grundy number of any graph in this class. Our class intersects the class of P5-free graphs and strictly contains the class of P4-free graphs. More precisely, our result implies that the Grundy number can be computed in polynomial time for any graph of the following classes: P4-reducible, extended P4-reducible, P4-sparse, extended P4-sparse, P4-extendible, P4-lite, P4-tidy, P4-laden and extended P4-laden, which are all strictly contained in the fat-extended P4-laden class.
- 1 :
- INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
- 2 :
- Universidade Federal do Ceara
- Domaine : Informatique/Complexité
- inria-00639008, version 1
- http://hal.inria.fr/inria-00639008
- oai:hal.inria.fr:inria-00639008
- Contributeur :
- Soumis le : Lundi 7 Novembre 2011, 18:58:14
- Dernière modification le : Mercredi 31 Octobre 2012, 17:22:38




Documents associés
Exporter