28532 articles – 22057 Notices  [english version]

inria-00639008, version 1

On the Grundy number of graphs with few P4's

Julio Araujo () 12, Claudia Linhares Sales () 2

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 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • 2 :  Parallelism, Graphs and Optimization Research Group (ParGO)
  • Universidade Federal do Ceara
  • Domaine : Informatique/Complexité
 
  • inria-00639008, version 1
  • 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