← All problems

Naserasr’s fractional coloring conjecture

For every integer k≥1k\ge 1 and every planar graph GG whose odd girth is at least 2k+32k+3, the fractional chromatic number satisfies χf(G)≤2k+1k\chi_f(G)\le \frac{2k+1}{k}.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A 2026 preprint reports a stronger finite-size bound related to Naserasr’s conjecture, but the full conjecture remains open.

Naserasr conjectured that planar graphs with sufficiently large odd girth have fractional chromatic number at most 2s+1s\frac{2s+1}{s}. The conjecture remains unresolved for general planar graphs.

Known results

  • Triangle-free planar graphs on nn vertices satisfy χf(G)≤3−32n+1\chi_f(G)\le 3-\frac{3}{2n+1}; this improves the earlier Dvořák–Sereni–Volec bound 3−33n+13-\frac{3}{3n+1}.
  • Jones constructed infinitely many triangle-free planar graphs with χf(G)≥3nn+1\chi_f(G)\ge \frac{3n}{n+1}, so these values approach 33.
  • For every odd k≥5k\ge 5, planar graphs of girth kk with no cycle lengths from k+1k+1 through ⌊22k3⌋\left\lfloor\frac{22k}{3}\right\rfloor satisfy the relevant fractional-coloring bound.

October 2026 finite-size strengthening

Xiaolan Hu, Jiaao Li, and Zhouningxin Wang report a strict finite-nn correction attaining the conjectured bound in the stated planar odd-girth setting, together with a sharper triangle-free planar estimate attained infinitely often. This is a claimed specialist preprint advance, not an independently verified resolution of the full conjecture.

Current status (as of October 2026): Naserasr’s conjecture remains open, while the Hu–Li–Wang preprint claims a quantitative finite-size advance and sharper extremal results in specified planar cases.

Sources

Solutions 0

No solutions have been posted yet.