# Shannon capacity determined by $\alpha(G)$ and $\chi^*(\bar{G})$???

Are there graphs where $\alpha(G) = \chi^*(\bar{G}) < \chi(\bar{G})$???

Here, $\chi^*(\bar{G})$ is the fractional chromatic number, which I believe is also equal to the fractional independence number by the duality of linear programming. The point is, since for all graphs we have

$$\alpha(G) \leq \Theta(G) \leq \chi^*(\bar{G}) \leq \chi(\bar{G})$$

where $\Theta(G)$ is the Shannon capacity, I'm wondering if there are graphs where the Shannon capacity is determined by $\alpha(G)$ and $\chi^*(\bar{G})$, but not by $\alpha(G)$ and $\chi(\bar{G})$.

Thanks

-

## 2 Answers

I will work with the complements. We first want a graph $G$ such that $\omega(G)$ (the maximum size of a clique) is equal to $\chi_f(G)$, its fractional chromatic number. Take $G$ to be the Kneser graph $K_{9:3}$; its vertices are the 84 triples from a set of size nine, with two triples adjacent if they are disjoint. So $\omega(G)=3$ and $\alpha(G)=28$ (by the EKR theorem). Since $G$ is vertex transitive, $$\chi_f(G) = |V(G)|/\alpha(G) = 3.$$ By a theorem of Lovasz, $\chi(K_{v:k})=v-2k+2$ and so $\chi(G)=5$.

In fact $K_{3k:k}$ works whenever $k\ge2$.

-

The line graph of the Petersen graph has clique number 3, fractional chromatic number 3, and chromatic number 4. Therefore its complement has the property you want.

-