Skip to main content

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $\chi \(\overline{G})$$\chi (\overline{G})$. 

When $G$ is perfect then $$\alpha(G)=\vartheta(G)=\chi \(\overline{G}).$$ Give examples of$$\alpha(G)=\vartheta(G)=\chi (\overline{G}).$$

I would like to know if there are graphs $G$, such that $$\alpha(G)<\vartheta(G)=\chi \(\overline{G}).$$$$\alpha(G)< \vartheta(G)= \chi (\overline{G}).$$

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $\chi \(\overline{G})$. When $G$ is perfect then $$\alpha(G)=\vartheta(G)=\chi \(\overline{G}).$$ Give examples of graphs $G$ such that $$\alpha(G)<\vartheta(G)=\chi \(\overline{G}).$$

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $\chi (\overline{G})$. 

When $G$ is perfect then $$\alpha(G)=\vartheta(G)=\chi (\overline{G}).$$

I would like to know if there are graphs $G$, such that $$\alpha(G)< \vartheta(G)= \chi (\overline{G}).$$

Source Link
user3409
user3409

When the Lovász theta-function saturates its upper bound

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $\chi \(\overline{G})$. When $G$ is perfect then $$\alpha(G)=\vartheta(G)=\chi \(\overline{G}).$$ Give examples of graphs $G$ such that $$\alpha(G)<\vartheta(G)=\chi \(\overline{G}).$$