Fractional chromatic number of {C₄,C₅}-free planar graphs
Problem 1.3 · arXiv:1802.04179
Status partial high confidence
The exact infimum of fractional chromatic numbers of planar graphs without cycles of length 4 or 5 remains open. The original upper bound of 11/3 from the source paper was subsequently improved to 7/2 by Wang (referenced in arXiv:2511.12914). A November 2025 paper (arXiv:2511.12914) further establishes that these graphs are (7m:2m)-DP-colorable for every positive integer m, confirming the 7/2 upper bound via DP-coloring. The lower bound is 3, so the infimum lies in [3, 7/2].
Cited literature (1)
-
Proves that planar graphs without cycles of length 4 or 5 are (7m:2m)-DP-colorable for any positive integer m, extending Wang's (7:2)-colorability result and improving the upper bound on the fractional chromatic number from 11/3 to 7/2.
Reviewer notes. Wang's paper proving (7:2)-colorability is cited in arXiv:2511.12914 but its full bibliographic details (title, year, venue, arXiv ID) could not be retrieved within the 5-call budget. The 2511.12914 paper was verified via WebFetch. The conjecture (exact infimum) remains open with best known bounds 3 ≤ inf ≤ 7/2.
Context
The authors prove that every planar graph without cycles of length 4 or 5 is $(11:3)$-colorable, giving an upper bound of $\frac{11}{3}$ on the fractional chromatic number. They note the counterexample to Steinberg's conjecture from [4] is $(6:2)$-colorable, so the answer could be as low as $3$.
Source paper
Planar graphs without cycles of length 4 or 5 are (11:3)-colorable
Zdeněk Dvořák, Xiaolan Hu · 2019-07-14
https://arxiv.org/abs/1802.04179
PDF source