Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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

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

Your Answer

 
discard

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.