Critical 3-cochromatic graphs (Q1900522)

A \(k\)-cocolouring of a graph \(G\) is a colouring of the vertices of \(G\) in \(k\) colours such that, for every colour, the subgraph induced by the vertices of that colour is either a complete graph or an edgeless graph. A graph \(G\) is \(k\)-cochromatic if \(k\) is the smallest number such that \(G\) has a \(k\)-cocolouring. If \(G\) is \(k\)-cochromatic and, for every vertex \(x\) of \(G\), the graph \(G - x\) is \((k - 1)\)-cochromatic then \(G\) is a critical \(k\)-cochromatic graph. In this paper it is shown that every critical 3-cochromatic graph is either an odd cycle or the complement of an odd cycle, or one of 42 graphs on 6 vertices.