Restricted coloring problems on Graphs with few P4’s

In this paper, we obtain linear time algorithms to determine the acyclic chromatic number, the star chromatic number, the non repetitive chromatic number and the clique chromatic number of P4-tidy graphs and (q, q − 4)-graphs, for every fixed q, which are the graphs such that every set with at most q vertices induces at most q − 4 distinct P4’s. These classes include cographs and P4-sparse graphs. We also obtain a linear time algorithm to compute the harmonious chromatic number of connected P4-tidy graphs and connected (q, q − 4)-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, generalizing the main result of Lyons (2011).