On the Grundy number of graphs with few \(P_4\)'s (Q1759824): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2011.08.016 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2014098222 / rank | |||
Normal rank |
Revision as of 02:13, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Grundy number of graphs with few \(P_4\)'s |
scientific article |
Statements
On the Grundy number of graphs with few \(P_4\)'s (English)
0 references
22 November 2012
0 references
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.
0 references
Grundy number
0 references
\(P_4\)-classes
0 references
modular decomposition
0 references