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

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

Your Answer


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

Browse other questions tagged or ask your own question.