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?


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.