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

Let $G$ be a graph with maximum degree 4 and clique number 2. The fractional version of Reed's Conjecture tells us that $\chi_f(G) \leq 7/2$. But how high can $\chi_f(G)$ be?

The Chvátal graph has fractional chromatic number 3. The Grünbaum graph on 25 vertices has stability number 8, and therefore has fractional chromatic number at least $25/8$.

Update: The graph pictured below, from "A note on 4-regular 4 chromatic graphs with girth 4" by Song, Wang, Yao, and Zhang, has stability number 4 and 13 vertices, and therefore has fractional chromatic number at least $13/4$; Nathann Cohen provided a proof that indeed $\chi_f=13/4$ for this graph.

Let $z$ be the maximum fractional chromatic number of a triangle-free graph with maximum degree 4. Then $$ \frac{13}{4} \leq z \leq \frac{14}4. $$ Are better bounds possible?

Worst case?

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.