SET COLORINGS OF GRAPHS

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 x(r)(G) the minimum number of colours required to r-set colour G. The set-chromatic number of G, denoted by x* (G), is defined by x*(G)=infr x(r)(G) r. Clearly 2≤ x*(G)≤x(G). By making use of a recent result of L. Lovász we prove that min {x(r)(G): x(G) = k}= 2r+k-2 and min{x(r)(G):G is uniquely k-colourable} = 2r+k-1. In particular, given any k, x*(G) may be arbitrarily close to 2, and given any r, the ratio x(r)(H)/x(H) may be arbitraril close to 1, even if H is uniquely colourable. The results disprove a conjecture of D.P. Geller. © 1979.