Skip to main content
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Source Link

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

As noted herehere, 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$?

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

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

Source Link

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