Take the 2-minute tour ×

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


share|improve this question

2 Answers 2

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

share|improve this answer

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.

share|improve this answer

Your Answer


