On the Grundy number of graphs with few \(P_4\)'s
type: Item
instance of: scholarly article
title: On the Grundy number of graphs with few \(P_4\)'s
zbMATH Open document ID: 1296.05065
published in: Discrete Applied Mathematics
publication date: 2012-11-22T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6109900
zbMATH Keywords: Grundy number
zbMATH Keywords: \(P_4\)-classes
zbMATH Keywords: modular decomposition
author: Júlio Araújo
author: Cláudia L. Sales
reviewed by: Gabriel Semanišin
MaRDI profile type: Publication
full work available at URL: j.dam.2011.08.016
OpenAlex ID: W2014098222
cites work: Four classes of perfectly orderable graphs
cites work: Q4193514
cites work: \(P_{4}\)-laden graphs: A new class of brittle graphs
cites work: A coloring problem for weighted graphs
cites work: On-line and first fit colorings of graphs
cites work: Q3496352
cites work: The splittance of a graph
cites work: Q4745272
cites work: Q4243805
cites work: Reducibility among Combinatorial Problems
cites work: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
cites work: Algorithms for Vertex Partitioning Problems on Partial k-Trees
cites work: Q4659607
cites work: Results on the Grundy chromatic number of graphs
DOI: 10.1016/J.DAM.2011.08.016
description: scientific article; zbMATH DE number 6109900