Nonrepetitive, acyclic and clique colorings of graphs with few P4's

In this paper, we propose algorithms to determine the Thue chromatic number and the clique chromatic number of P4-tidy graphs and (q,q − 4)-graphs. These classes include cographs and P4-sparse graphs. All algorithms have linear-time complexity, for fixed q, and then are fixed parameter tractable. All these coloring problems are known to be NP-hard for general graphs. 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 a result from [28]. Finally, we show that the algorithm from [31] can also be used to compute the acyclic chromatic number of distance hereditary graphs and graphs with a given split decomposition tree with bounded width.