An Upper Bound on the Fractional Chromatic Number

Abstract

An (a:b)-coloring of a graph G is a function f which maps the vertices of G into b-element subsets of some set of size a in such a way that f(u) is disjoint from f(v) for every two adjacent vertices u and v in G. The fractional chromatic number \chi_f(G) is the infimum of a/b over all pairs of positive integers a,b such that G has an (a:b)-coloring. Heckman and Thomas conjectured that the fractional chromatic number of every triangle-free graph G of maximum degree at most three is at most 2.8. Hatami and Zhu proved that \chi_f(G) \leq 3-3/64 \approx 2.953. Lu and Peng improved the bound to \chi_f(G) \leq 3-3/43 \approx 2.930. Recently, Ferguson, Kaiser and Kral proved that \chi_f(G) \leq 32/11 \approx 2.909. In this talk, I will prove that \chi_f(G) \leq 43/15 \approx 2.867.