Grundy number on P4-classes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Grundy number on P4-classes

Résumé

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 the graphs in this class. This result implies that the Grundy number can be found 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.
Fichier principal
Vignette du fichier
grundy_p4-final.pdf (104.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00531691 , version 1 (04-11-2010)

Identifiants

Citer

Julio Araujo, Claudia Linhares Sales. Grundy number on P4-classes. LAGOS'09 – V Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2009, Gramado, Brazil. pp.21-27, ⟨10.1016/j.endm.2009.11.005⟩. ⟨inria-00531691⟩
190 Consultations
193 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More