## Abstract

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.

Original language | English |
---|---|

Journal | SIAM Journal on Discrete Mathematics |

Volume | 33 |

Issue number | 3 |

Pages (from-to) | 1415-1430 |

Number of pages | 16 |

ISSN | 0895-4801 |

DOIs | |

Publication status | Published - 1 Jan 2019 |

## Keywords

- Degeneracy
- Fractional chromatic number
- Graphs on surfaces
- Planar graphs