The Fractional Chromatic Number of Triangle-free Graphs with $\Delta \le 3$

Abstract

Let $G$ be any triangle-free graph with maximum degree $\Delta \le 3$. Staton proved that the independence number of $G$ is at least 5/14n. Heckman and Thomas conjectured that Staton's result can be strengthened into a bound on the fractional chromatic number of $G$, namely ${\chi }_f(G)\le 14/5.Recently,HatamiandZhuproved$χ_f(G) \leq 3 -{3/64}$.Inthispaper,weprove$χ_f(G) \leq 3- 3/43$.

arXiv commentSecond revision: typos fixed, 24 pages, 37 figures