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

Improve this question
$\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$
    – Emil Jeřábek
    Commented 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$
    – Dominic van der Zypen
    Commented Jan 29, 2015 at 14:07

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .