# When the vertex covering number is smaller than the chromatic number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$.

As noted here, we have $\tau(G) \geq \chi(G) - 1$ for all finite graphs $G$. I'm interested in graphs $G$ with $\tau(G) = \chi(G) - 1$. I found only examples of such graphs where $\chi(G) = \omega(G)$ (where $\omega(G)$ is the clique number of $G$).

Question: Is there a graph $G$ with $\omega(G) < \chi(G)$ and $\tau(G) = \chi(G) - 1$?

• The linked argument actually shows that $\chi(G)\le1+\chi(C)$, where $C$ is the subgraph induced by a minimal vertex cover. So, $\tau(G)\ge\chi(G)$ unless $C$ is a clique. For much the same reason, $\tau(G)\ge\chi(G)$ unless one vertex from $V-C$ is connected to everyone in $C$. So, no, there isn’t such a graph. – Emil Jeřábek Jan 29 '15 at 13:13
• Thank you very much - can you post this as an answer so that I can accept it and we can close this thread? – Dominic van der Zypen Jan 29 '15 at 14:07

Expanding a bit the construction given by Leen Droogendijk on MSE, let $C$ be a vertex cover of minimal size. Then we can colour $G$ by colouring $C$ (considered as an induced subgraph), and giving all vertices of $V-C$ an extra colour. This shows $$\chi(G)\le1+\chi(C),$$ hence $\tau(G)=\chi(G)-1$ can only happen if $\chi(C)=|C|$, i.e., $C$ is a clique.
Furthermore, if $v\in V-C$ is not connected by an edge to some $u\in C$, we can colour $v$ the same as $u$ (here we use that vertices from $C$ have pairwise distinct colours). Thus, we can save the extra colour altogether unless some $v\in V-C$ is connected to all vertices in $C$, in which case $C\cup\{v\}$ is a clique of size $|C|+1=\chi(G)$. All in all, $\tau(G)=\chi(G)-1$ implies $\chi(G)=\omega(G)$.