Skip to Main content Skip to Navigation
New interface
Journal articles

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 , Laboratoire I3S - 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00639008
Contributor : Julio Araujo Connect in order to contact the contributor
Submitted on : Monday, November 7, 2011 - 6:58:14 PM
Last modification on : Thursday, August 4, 2022 - 4:52:40 PM
Long-term archiving on: : Wednesday, February 8, 2012 - 2:36:31 AM

File

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

Identifiers

Collections

Citation

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

Share

Metrics

Record views

320

Files downloads

164