| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652438 | Electronic Notes in Discrete Mathematics | 2009 | 7 Pages |
Abstract
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 the graphs in this class. This result implies that the Grundy number can be found 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
