Restricted coloring problems on graphs with few

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.