On the Grundy number of graphs with few P4's

Julio Araujo 1, 2 Claudia Linhares Sales 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization 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 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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2012, 160 (18), pp.2514-2522. <10.1016/j.dam.2011.08.016>
Liste complète des métadonnées


https://hal.inria.fr/inria-00639008
Contributeur : Julio Araujo <>
Soumis le : lundi 7 novembre 2011 - 18:58:14
Dernière modification le : mercredi 31 octobre 2012 - 17:22:38
Document(s) archivé(s) le : mercredi 8 février 2012 - 02:36:31

Fichier

grundy_p4-full-withmodifs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julio Araujo, Claudia Linhares Sales. On the Grundy number of graphs with few P4's. Discrete Applied Mathematics, Elsevier, 2012, 160 (18), pp.2514-2522. <10.1016/j.dam.2011.08.016>. <inria-00639008>

Partager

Métriques

Consultations de
la notice

241

Téléchargements du document

127