### 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

### Cite this

*SIAM Journal on Discrete Mathematics*,

*33*(3), 1415-1430. https://doi.org/10.1137/18M1177317

}

*SIAM Journal on Discrete Mathematics*, vol. 33, no. 3, pp. 1415-1430. https://doi.org/10.1137/18M1177317

**Fractional coloring methods with applications to degenerate graphs and graphs on surfaces.** / Gimbel, John; Kündgen, André; Li, Binlong; Thomassen, Carsten.

Research output: Contribution to journal › Journal article › Research › peer-review

TY - JOUR

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

AU - Gimbel, John

AU - Kündgen, André

AU - Li, Binlong

AU - Thomassen, Carsten

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 Kd +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.

AB - 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 Kd +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.

KW - Degeneracy

KW - Fractional chromatic number

KW - Graphs on surfaces

KW - Planar graphs

U2 - 10.1137/18M1177317

DO - 10.1137/18M1177317

M3 - Journal article

VL - 33

SP - 1415

EP - 1430

JO - S I A M Journal on Discrete Mathematics

JF - S I A M Journal on Discrete Mathematics

SN - 0895-4801

IS - 3

ER -