Uniquely cocolourable graphs (Q1079577)

A cocolouring of a graph G is a partition of the vertex set of G in such a way that each set of the partition induces an empty or a complete graph in G. The cochromatic number of G, denoted by z(G), is the minimum number of colours needed in any cocolouring of G. A graph G with \(z(G)=n\) is uniquely n-cocolourable if all n-cocolourings of G induce the same partition of V(G). In this paper it is proved that for each natural number n there are infinitely many uniquely n-cocolourable graphs and that the numbers of complete and empty colour classes can be prescribed. It is also shown that every n-cocolourable graph is an induced subgraph of a uniquely n-cocolourable graph.