MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.