7
$\begingroup$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.