5
$\begingroup$

The following statement seems very plausible: If $G$ is a triangle-free graph of degeneracy $d$, then $$ \chi_f(G) \leq O(\frac{d}{\log d}) $$ where $\chi_f$ is the fractional chromatic number.

This statement would be false if $\chi_f$ is replaced with the ordinary chromatic number $\chi$; Alon, Krivelevich, Sudakov give a counter-example of a $d$-degenerate graph with chromatic number $d$. However, their counter-example also has fractional chromatic number $O(d/\log d)$.

I could not find any reference to this statement, either stating it as a known conjecture or giving a proof. Is this known anywhere?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .