2
$\begingroup$

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

$\endgroup$
2
  • 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$ Jan 29, 2015 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$ Jan 29, 2015 at 14:07

1 Answer 1

4
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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