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 P4’s. In particular we shall consider the classes of extended P4-laden graphs, p-trees (graphs which contain exactly n?3 P4’s) and (q,q?3)-graphs, q≥7, such that no set of at most q vertices induces more that q?3 distincts P4’s. As corollary we shall derive the clique-chromatic number and the clique-colouring of the classes of cographs, P4-reducible graphs, P4-sparse graphs, extended P4-reducible graphs, extended P4-sparse graphs, P4-extendible graphs, P4-lite graphs, P4-tidy graphs and P4-laden graphs that are included in the class of extended P4-laden graphs.