Skip to main content
1 of 3
JonCC
  • 211
  • 1
  • 5

Is there a term for this graph subset?

Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:

If $c:V(G)\rightarrow [k]$ is a vertex colouring of $G$ with $k$ colours, then the restriction of $c$ to $S$ is surjective. In other words, $c(S)=[k]$. That is, whenever the vertices of $G$ are coloured with $k$ colours, every colour appears at least once on $S$.

I would like to know the technical term (if there is one) for this property of $S$. I have been unable to find information on this concept online. When I first considered such sets, I called $S$ a "$k$-rainbow set" for $G$. However, I quickly realised that this term is already used in reference to "rainbow paths", which is a very different concept.

References to any research that has been done on these sets would also be greatly appreciated.

JonCC
  • 211
  • 1
  • 5