The existence of uniquely \(-G\) colourable graphs (Q1377702): Difference between revisions

Given graphs \(F\) and \(G\) and a nonnegative integer \(k\), a function \(\pi :V(F)\rightarrow \{1,\ldots ,k\}\) is a \(-G\) \(k\)-colouring of \(F\) if no induced copy of \(G\) is monochromatic; \(F\) is \(-G\) \(k\)-chromatic if \(F\) has a \(-G\) \(k\)-colouring but no \(-G\) \((k-1)\)-colouring. Further, we say \(F\) is uniquely \(-G\) \(k\)-colourable if \(G\) is \(-G\) \(k\)-chromatic and, up to a permutation of colours, it has only one \(-G\) \(k\)-colouring. It was conjectured by \textit{J. I. Brown} and \textit{D. G. Corneil} [J. Graph Theory 11, 87-99 (1987; Zbl 0608.05035)] that uniquely \(-G\) \(k\)-colourable graphs exist for all graphs \(G\) of order at least 2 and all positive integers \(k\). What has been known so far is that the conjecture holds whenever \(G\) or its complement has a universal vertex or is 2-connected. In this paper the conjecture is completely settled by showing that, in fact, in all cases infinitely many such graphs exist.