Perfect Colourings

Given a graph \(G\) and nonnegative integer \(k\), a map \(\pi: V(G) \to \{1, \ldots, k\}\) is a perfect \(k\)-colouring if the subgraph induced by each colour class is perfect. The perfect chromatic number of \(G\) is the least \(k\) for which \(G\) has a perfect \(k\)-colouring; such an invariant is a measure of a graph’s imperfection. We study here the theory of perfect colourings. In particular, the existence of perfect \(k\)-chromatic graphs are shown for all \(k\), and we draw attention to the associated extremal problem. We provide extensions to C. Berge’s Strong Perfect Graph Conjecture, and prove the existence of graphs with only one perfect \(k\)-colouring (up to a permutation of colours). The type of approach taken here can be applied to studying any graph property closed under induced subgraphs.