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

26 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

Cite this

@article{b63bb9a2d3024547b82ca44271c2f4af,
title = "Fractional coloring methods with applications to degenerate graphs and graphs on surfaces",
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{\"o}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{\"o}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.",
keywords = "Degeneracy, Fractional chromatic number, Graphs on surfaces, Planar graphs",
author = "John Gimbel and Andr{\'e} K{\"u}ndgen and Binlong Li and Carsten Thomassen",
year = "2019",
month = "1",
day = "1",
doi = "10.1137/18M1177317",
language = "English",
volume = "33",
pages = "1415--1430",
journal = "S I A M Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics",
number = "3",

}

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

In: SIAM Journal on Discrete Mathematics, Vol. 33, No. 3, 01.01.2019, p. 1415-1430.

Research output: Contribution to journalJournal articleResearchpeer-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 -