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$?

  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 29 '15 at 13:13
  • $\begingroup$ Thank you very much - can you post this as an answer so that I can accept it and we can close this thread? $\endgroup$ – 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)$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.