On the Grundy number of graphs with few P4P4’s

The Grundy number of a graph GG is the largest number of colors used by any execution of the greedy algorithm to color GG. The problem of determining the Grundy number of GG is polynomial if GG is a P4P4-free graph and NPNP-hard if GG is a P5P5-free graph. In this article, we define a new class of graphs, the fat-extended P4P4-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 P5P5-free graphs and strictly contains the class of P4P4-free graphs. More precisely, our result implies that the Grundy number can be computed in polynomial time for any graph of the following classes: P4P4-reducible, extended P4P4-reducible, P4P4-sparse, extended P4P4-sparse, P4P4-extendible, P4P4-lite, P4P4-tidy, P4P4-laden and extended P4P4-laden, which are all strictly contained in the fat-extended P4P4-laden class.

► We introduce a new class of graphs, the fat-extended P4P4-laden graphs.► Polynomial time algorithm to calculate the Grundy number of any graph of this class.► Our class intersects the class of the P5P5-free graphs.► Strictly contains the class of P4P4-free graphs.