Fractional coloring methods with applications to degenerate graphs and graphs on surfaces

We study methods for finding strict upper bounds on the fractional chromatic number χ_f(G) of a graph G. We illustrate these methods by providing short proofs of known inequalities in connection with Grötzsch’s 3-color theorem and the 5-color theorem for planar graphs. We also apply it to d-degenerate graphs and conclude that every K_{d +1}-free d-degenerate graph with n vertices has independence number < n/(d + 1). We show that for each surface S and every ε > 0, the fractional chromatic number of any graph embedded on S of sufficiently large width (depending only on S and ε) is at most 4 + ε. In the same spirit we prove that Eulerian triangulations or triangle-free graphs of large width have χ_f ≤ 3 + ε, and quadrangulations of large width have χ_f ≤ 2 + ε. While the ε is needed in the latter two results, we conjecture that in the first result 4 + ε can be replaced by 4. The upper bounds χ_f ≤ 4 + ε, χ_f ≤ 3 + ε, χ_f ≤ 2 + ε, respectively, are already known for graphs on orientable surfaces, but our results are also valid for graphs on nonorientable surfaces. Surprisingly, a strict lower bound on the fractional chromatic number may imply an upper bound on the chromatic number: Grötzsch’s theorem implies that every 4-chromatic planar graph G has fractional chromatic number χ_f(G) ≥ 3. We conjecture that this inequality is always strict and observe that this implies the 4-color theorem for planar graphs.