On the Grundy number of graphs with few \(P_4\)'s (Q1759824): Difference between revisions

The paper deals with the Grundy number, that is, the largest number of colours used by any execution of the greedy algorithm to colour a graph \(G\). It is known that the problem of determining the Grundy number of \(G\) is polynomial if \(G\) is a \(P_4\)@-free graph and NP@-hard if \(G\) is a \(P_5\)-free graph. The authors define the class of fat-extended \(P_4\)@-laden graphs as a modification of already introduced extended \(P_4\)@-laden graphs. They design a polynomial-time algorithm to determine the Grundy number of any graph in this class. Since this new class intersects the class of \(P_5\)-free graphs and strictly contains the class of \(P_4\)-free graphs, this implies that the Grundy number can be computed in polynomial time for any graph in a few classes closely related to the studied class.