Is there a name for this type of graph colouring?

82 Views Asked by At

Suppose $G$ is a (finite) graph and $S\subseteq V(G)$ is a set of vertices of $G$. Suppose $G$ is $k$-vertex colourable (i. e. $G$ has chromatic number at most $k$). We say that $S$ is a "$k$-painting" for $G$ (non-standard terminology) if for all $k$-vertex colourings of $G$, every colour must appear in $S$.

I. e. if $c\colon V(G)\rightarrow [k]$ is a colouring of the vertices of $G$ with $k$ colours, then the restriction of $c$ to $S$ is surjective (that is, $c(S)=[k]$).

E. g. if $S$ is a clique of $G$ of size $k=\chi (G)$, then $S$ is a $k$-painting of $G$. In particular, if $G$ is bipartite, any two adjacent vertices of $G$ form a 2-painting. Note that in general we can have $k$-paintings which are not cliques and are of size greater than $k$ (e. g. $\{1,4,7\}$ in an 8-cycle).

The name "$k$-painting" is my own placeholder for this property. I have been unable to find any references to this property online (originally I called it a "$k$-rainbow set for $G$", but there is already a concept of rainbow paths which is very different).

I am hoping that someone can tell me the standard name (if there is one) for this property. References to any research that has been done in this area would also be greatly appreciated.