Colour Transversal Vertex Covering Set

NEW

Problem: For finite simple graphs, let $\chi(G)$ be the chromatic number. Let $\alpha_*(G)$ be the minimum size of a vertex cover $T\subseteq V(G)$ that meets every color class in some proper $\chi(G)$-coloring of $G$. The conjecture states:

This is the natural formalization of “colour transversal vertex covering number” in Thakkar–Dave.

Result: The conjecture is true.

Let $\tau(G)$ be the ordinary vertex-cover number and $\beta(G)$ the independence number. Since complements of vertex covers are independent,

First note that for every finite graph $F$,

The lower bound is immediate. For the upper bound, take a maximum independent set $I$. Then $V(F)\setminus I$ is a minimum vertex cover. In any $\chi(F)$-coloring, at most one color class can lie wholly inside $I$, since two such color classes could be merged. Thus adding, if necessary, one vertex from the unique missed color class gives a CTVC set of size at most $\tau(F)+1$.

Now put $H=G-v$. Deleting one vertex changes $\tau$ by at most one:

If $\tau(H)\le \tau(G)-1$, then

so we are done.

It remains to consider $\tau(H)=\tau(G)$. Let $|V(G)|=n$. Then

so $\beta(G)=\beta(H)+1$. Hence every maximum independent set of $G$ contains $v$; write one as $J\cup\{v\}$, where $J$ is a maximum independent set of $H$. In particular, $v$ has no neighbor in $J$.

Let $T=V(H)\setminus J$. Then $T$ is a minimum vertex cover of $H$, so $|T|=\tau(H)$. Let $r=\chi(H)$. Since $\chi(G)>r$, no $r$-coloring of $H$ extends to $G$. Therefore, in every $r$-coloring of $H$, the vertex $v$ has a neighbor in every color class. But $v$ has no neighbors in $J$, so each color class meets $T$. Hence $T$ is a CTVC set of $H$, and

Thus always

Citation: D.K. Thakkar and V.R. Dave, “Colour Transversal Vertex Covering Set,” International Journal of Scientific and Innovative Mathematical Research 4(5) (2016), 37–44, Conjecture 3.1. The proof above is self-contained; I am not aware of a prior published resolution.