4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.