On clique-colouring of graphs with few P 4’s

摘要

Let G =( V , E ) be a graph with n vertices. A? clique-colouring of a graph is a colouring of its vertices such that no maximal clique of size at least two is monocoloured. A k -clique-colouring is a clique-colouring that uses k colours. The clique-chromatic number of a graph G is the minimum k such that G has a k -clique-colouring. In this paper we will use the primeval decomposition technique to find the clique-chromatic number and the clique-colouring of well known classes of graphs that in some local sense contain few P ~(4)’s. In particular we shall consider the classes of extended P ~(4)-laden graphs, p -trees (graphs which contain exactly n ?3 P ~(4)’s) and ( q , q ?3)-graphs, q ≥7, such that no set of at most q vertices induces more that q ?3 distincts P ~(4)’s. As corollary we shall derive the clique-chromatic number and the clique-colouring of the classes of cographs, P ~(4)-reducible graphs, P ~(4)-sparse graphs, extended P ~(4)-reducible graphs, extended P ~(4)-sparse graphs, P ~(4)-extendible graphs, P ~(4)-lite graphs, P ~(4)-tidy graphs and P ~(4)-laden graphs that are included in the class of extended P ~(4)-laden graphs.