Weighted odd-cycle transversals and fractional colorings of planar graphs

Source abstract

We bound fractional chromatic numbers by establishing a connection with low-weight odd-cycle transversals. Let $\ell\geq 3$ be an integer and let $G$ be a graph of odd girth at least $\ell$ whose odd-cycle covering polyhedron is integral. For every nonnegative weight vector $w=(w_v)_{v\in V(G)}\in \mathbb{R}_{\geq 0}^{V(G)}$, we obtain a set $Z\subseteq V(G)$ such that $G-Z$ is bipartite and $w(Z)\leq\frac{mad(G)}{2\ell}w(V(G))$. Here, $w(S)=\sum_{v\in S}w_v$ for any $S\subseteq V(G)$, and $mad(G)$ denotes the maximum average degree of $G$. Consequently, if $mad(G)<2\ell$, then $G$ has fractional chromatic number at most $\frac{4\ell}{2\ell-mad(G)}$. As applications, we prove that, for every positive integer $k$, every $n$-vertex planar graph of girth at least $2k+3$ has fractional chromatic number at most $\frac{2k+1}{k}(1-\frac{1}{kn+1})$, establishing the girth version of Naserasr's fractional coloring conjecture with a strict inequality. For $k=1$, we furthermore prove that the upper bound $\frac{3n}{n+1}$ holds for every $n$-vertex triangle-free planar graph and this is attained for infinitely many values of $n$.