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

John Gimbel, André Kündgen, Binlong Li, Carsten Thomassen

Research output: Contribution to journalJournal articleResearchpeer-review

385 Downloads (Pure)

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

Original languageEnglish
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number3
Pages (from-to)1415-1430
Number of pages16
ISSN0895-4801
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

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

Fingerprint Dive into the research topics of 'Fractional coloring methods with applications to degenerate graphs and graphs on surfaces'. Together they form a unique fingerprint.

Cite this