Bounding the fractional chromatic number of $K_{\Delta }$-free graphs

Abstract

King, Lu, and Peng recently proved that for $\Delta \ge 4$, any $K_{\Delta }$-free graph with maximum degree $\Delta$ has fractional chromatic number at most $\Delta -\frac{2}{67}$ unless it is isomorphic to $C_5⊠K_2$ or $C_8^2$. Using a different approach we give improved bounds for $\Delta \ge 6$ and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's $\omega$, $\Delta$, $\chi$ conjecture.

30 pages, revised edition