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.

An \(S_{s,t}\) distar-factorization of \(DK_{m}\) is an edge partitioning of the complete symmetric directed graph \(DK_{m}\) into subdigraphs each of which is isomorphic to the distar \(S_{s,t}\) (the distar \(S_{s,t}\) being obtained from the star \(K_{1,s+t}\) by directing \(s\) of the edges into the centre and \(t\) of the edges out of the centre). We consider the question, “When can the arcs of \(DK_{m}\) be partitioned into arc-disjoint subgraphs each isomorphic to \(S_{s,t}\)?” and give necessary and sufficient conditions for \(S_{s,t}\) distar-factorizations of \(DK_{m}\) in the cases when either \(m\equiv 0\) or \(1 \pmod{s+t}\).