Set colourings of graphs. (Reprint) (Q2497995)

This article is a reprint of an important paper published in Discrete Math. 25, 21--26 (1979; Zbl 0403.05038). An \(r\)-set colouring of a graph \(G\) is an assignment of \(r\) distinct colours to each vertex of \(G\) so that the sets of colours assigned to adjacent vertices are disjoint. We denote by \(\chi^{(r)} (G)\) the minimum number of colours required to \(r\)-set colour \(G\). The set-chromatic number of \(G\), denoted by \(\chi^*(G)\), is defined by \(\chi^* (G) = \inf_r \chi^{(r)} (G) / r\). Clearly \( 2 \leq \chi^* (G) \leq \chi (G)\). By making use of a recent result of L. Lovász we prove that \(\min \{ \chi^{(r)} (G) \;:\;\chi(G) = k \} = 2r + k - 2\) and \(\min \{ \chi^{(r)} (G) \;:\;G\) is uniquely \(k\)-colourable\(\} = 2r + k - 1\). In particular, given any \(k\), \(\chi^*(G)\) may be arbitrarily close to 2, and given any \(r\), the ratio \(\chi^{(r)}(G)/\chi(G)\) may be arbitrarily close to 1, even if \(G\) is uniquely colourable. The results disprove a conjecture of D.P. Geller.