| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652589 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of P4-tidy graphs and (q,q−4)-graphs, for every fixed q. These classes include cographs, P4-sparse and P4-lite graphs. We also obtain a polynomial time algorithm to determine the Grundy number of (q,q−4)-graphs. All these coloring problems are known to be NP-hard for general graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
