A clique-colouring of a graph is a colouring of its vertices such that no
maximal clique of size at least two is monocolored. 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 work we will use the primeval decomposition technique to find the
clique-chromatic number and the clique-colouring of graphs with few P_4's.
In particular we will consider the class of (q,q-3)-graphs such that no set
of at most q vertices induces more than q-3 distincts P_4's. This class
contains many well known classes of graphs such as: cographs, P_4-reducible,
P_4-sparse, p-trees, p-forests, etc.
This is a joint work with Aurora Morgana from
Universita di Roma "La Sapienza".