
AbstractAn 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 χ(r)(G) the minimum number of colours required to r-set colour G. The set-chromatic number of G, denoted by χ*(G), is defined byχ*(G)=infrχ(r)(G)r.Clearly 2⩽χ*(G)⩽χ(G).By making use of a recent result of L. Lovász we prove that min{χ(r)(G):χ(G)=k}=2r+k-2andmin{χ(r)(G):Gisuniquelyk-colourable}=2r+k-1. In particular, given any k,χ*(G) may be arbitrarily close to 2, and given any r, the ratio χ(r)(H)/χ(H) may be arbitrarily close to 1, even if H is uniquely colourable. The results disprove a conjecture of D.P. Geller.
R-set coloration, Coloring of graphs and hypergraphs, Kneser graph, R-set coloring, Discrete Mathematics and Combinatorics, Theoretical Computer Science
R-set coloration, Coloring of graphs and hypergraphs, Kneser graph, R-set coloring, Discrete Mathematics and Combinatorics, Theoretical Computer Science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 23 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
