An upper bound on the fractional chromatic number of triangle-free subcubic graphs

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)\le 3-3/64\approx 2.953$. Lu and Peng improved the bound to ${\chi }_f(G)\le 3-3/43\approx 2.930$. Recently, Ferguson, Kaiser and Král' proved that ${\chi }_f(G)\le 32/11\approx 2.909$. In this paper, we prove that ${\chi }_f(G)\le 43/15\approx 2.867$.

References in corpus (2)

• Linear colorings of subcubic graphs
• Subcubic triangle-free graphs have fractional chromatic number at most 14/5

Cited by in corpus (2)

• Spotting Trees with Few Leaves
• The fractional chromatic number of $K_{\Delta }$-free graphs