An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs Academic Article uri icon


  • 2014 Society for Industrial and Applied Mathematics. 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 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 f (G) 3 - 3/64 2. 953. Lu and Peng improved the bound to f (G) 3 - 3/43 2.930. Recently, Ferguson, Kaiser, and Krl' proved that f (G) 32/11 2.909. In this paper, we prove that f (G) 43/15 2.867.

published proceedings

  • SIAM Journal on Discrete Mathematics

author list (cited authors)

  • Liu, C.

citation count

  • 1

complete list of authors

  • Liu, Chun-Hung

publication date

  • January 2014