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.

  • $\begingroup$ I guess you are confusing $k$-colorable and $k$-chromatic graphs. Obviously there is a described set $S$ in $k$-colorable graph $G$ if and only if $G$ is $k$-chromatic. $\endgroup$ – Smylic Jun 16 '17 at 0:52
  • $\begingroup$ @Smylic I am aware of the difference between colorable and chromatic in this context. In retrospect, the way I have written the statement does seem confusing. However, I chose colorable over chromatic simply to say that there is some way of colouring with $k$ colours without immediately assuming the existence of "$k$-paintings". Obviously, as you say, the existence of a $k$-painting is equivalent to $\chi (G)=k$. $\endgroup$ – JonCC Jun 16 '17 at 1:23
  • $\begingroup$ If $\chi(G) < k$ then there are $k$-colorings that don't have at least one color at all, so for any $S \subseteq V(G)$ there is a coloring such that at least one color is missing in $S$. $\endgroup$ – Smylic Jun 16 '17 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.