χ_f bound 3 - 3/(n+1) for planar triangle-free

Fractional Chromatic Number Bound for Planar Triangle-Free Graphs · arXiv:1606.06265

arXiv Informal medium confidence— first stated 2016-06-20

Authors: Zdeněk Dvořák, Tomáš Masařík, Jan Musílek, Ondřej Pangrác

Status open medium confidence

The conjecture that every n-vertex planar triangle-free graph satisfies chi_f(G) <= 3 - 3/(n+1) remains open. The special case for graphs of maximum degree at most 4 was confirmed prior to the 2016 source paper (cited as [6] therein); the best general bound at the time of posting was 3 - 3/(3n+1) (Dvořák–Sereni–Volec, EJC 2015). A 2018 paper by Dvořák (arXiv:1809.05439) on fractional coloring of girth-five planar graphs reports improvements for triangle-free planar graphs, but the exact improvement relative to the conjectured 3 - 3/(n+1) could not be confirmed from the abstract. No complete resolution of the full conjecture was found.

Cited literature (1)

partial Fractional coloring of planar graphs of girth five (2018)

Zdeněk Dvořák · arXiv preprint · arXiv:1809.05439

Proves fractional coloring results for triangle-free planar graphs (the abstract indicates a bound improving the general 3 - 3/(3n+1) result of Dvořák–Sereni–Volec), but the exact bound relative to the conjectured 3 - 3/(n+1) could not be verified from the abstract alone.

Reviewer notes. The conjectured bound 3 - 3/(n+1) is motivated by the tight independence-number lower bound alpha(G) >= (n+1)/3 via alpha(G) >= n/chi_f(G). The max-degree-4 special case was already established before the source paper. The general bound 3 - 3/(3n+1) (Dvořák–Sereni–Volec 2015, arXiv:1402.5331) predates the conjecture statement; arXiv:1809.05439 (Dvořák 2018) may improve this for triangle-free planar graphs but exact bound unverified. No post-2016 paper explicitly resolving the full conjecture was found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. The fractional chromatic number of $n$-vertex planar triangle-free graphs might be bounded by $3 - 3/(n+1)$.

Context

Since $\alpha(G) \geq |V(G)|/\chi_f(G)$, the bound $\alpha(G) \geq (n+1)/3$ from Steinberg–Tovey and Theorem 2 indicate this potential upper bound on $\chi_f$. Dvořák et al. [6] confirmed it for planar triangle-free graphs of maximum degree at most 4; in general only the weaker bound $3 - 3/(3n+1)$ is known.

Notes. Stated with hedged language ('might be bounded'); the paper presents it as a consequence suggested by its main results together with the known partial result for maximum degree at most 4.

Source paper

Triangle-free planar graphs with the smallest independence number
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek, Ondřej Pangrác · 2016-06-20
https://arxiv.org/abs/1606.06265 PDF source