11
$\begingroup$

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.

EDIT: A common observation made in the comments is that the existence of a "$k$-rainbow set" of $G$ is equivalent to $k=\chi (G)$. It then seems odd that the name is given in terms of $k$ rather than $\chi$. The reason I phrased it as such is because, when I originally came upon this idea, I was considering subgraphs of $G$ and looking at their "rainbow sets". Hence it was necessary to keep track of a varying $k$ which might be less than $\chi(G)$.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Hmm I do not know of any standard terminology for such a set, but it seems to be a natural concept. The property that you are describing is equivalent to saying that there does not exist a $(k-1)$-colouring of $S$ which extends to a proper colouring of $G$. So, perhaps a name like "non-$(k-1)$-extendible" would be appropriate. $\endgroup$
    – Jon Noel
    Commented Jun 16, 2017 at 8:03
  • 5
    $\begingroup$ Since $S$ may not have chromatic number $k$ by itself, it would be good to use terminology that doesn't suggest that it does. $\endgroup$
    – Joel David Hamkins
    Commented Jun 16, 2017 at 18:25
  • 3
    $\begingroup$ I think this is only interesting if $k= \chi(G)$ otherwise only the whole vertex set has this property. I'd use something like $\chi$-witness set or $\chi$-intersecting set (it intersects every color class) or always $\chi$-colored set (maybe ACC set as an abbreviation). $\endgroup$
    – Daniel Soltész
    Commented Jun 16, 2017 at 18:49
  • 1
    $\begingroup$ Such a set is a 'transversal' of every partition of the vertex-set into independent sets, so I'd maybe call it a 'chromatic transversal'. You might also say that it intersects every independent set $X$ for which $G - X$ is $(k-1)$-colourable. $\endgroup$
    – monkeymaths
    Commented Jun 19, 2017 at 9:00
  • 1
    $\begingroup$ @DominicvanderZypen Take a graph $H$ on n vertices that is $k$-colorable. Add $\binom{n}{k-1}$ extra vertices and join these to the $(k-1)$ sets of $H$. Then the resulting graph is still $k$-colorable, and the additional set of vertices is independent (or stable) satisfies the required property. $\endgroup$
    – Daniel Soltész
    Commented Jun 22, 2017 at 0:16

0

Reset to default

You must log in to answer this question.