Weighted odd-cycle transversals and fractional colorings of planar graphs

We bound fractional chromatic numbers by establishing a connection with low-weight odd-cycle transversals. Let $\mathrm{\ell }\ge 3$ be an integer and let $G$ be a graph of odd girth at least $\mathrm{\ell }$ whose odd-cycle covering polyhedron is integral. For every nonnegative weight vector $w=(w_v{)}_{v\in V(G)}\in {\mathbb{R}}_{\ge 0}^{V(G)}$, we obtain a set $Z\subseteq V(G)$ such that $G-Z$ is bipartite and $w(Z)\le \frac{mad(G)}{2\mathrm{\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\mathrm{\ell }$, then $G$ has fractional chromatic number at most $\frac{4\mathrm{\ell }}{2\mathrm{\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$.