In this paper, we obtain polynomial time algorithms to determine the acyclic
chromatic number, the star chromatic number, the Thue chromatic number, the
harmonious chromatic number and the clique chromatic number of $P_4$-tidy
graphs and $(q,q-4)$-graphs, for every fixed $q$. These classes include
cographs, $P_4$-sparse and $P_4$-lite graphs. All these coloring problems are
known to be NP-hard for general graphs. These algorithms are fixed parameter
tractable on the parameter $q(G)$, which is the minimum $q$ such that $G$ is a
$(q,q-4)$-graph. We also prove that every connected $(q,q-4)$-graph with at
least $q$ vertices is 2-clique-colorable and that every acyclic coloring of a
cograph is also nonrepetitive.