Skip to Main content Skip to Navigation
Conference papers

Grundy number on P4-classes

Julio Araujo 1 Claudia Linhares Sales 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00531691
Contributor : Julio Araujo <>
Submitted on : Thursday, November 4, 2010 - 3:02:58 PM
Last modification on : Monday, October 12, 2020 - 10:30:18 AM
Long-term archiving on: : Saturday, February 5, 2011 - 2:28:11 AM

File

grundy_p4-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

479

Files downloads

495