Bonamy–Kardos–Kelly–Postle conjecture on fractional arboricity of planar graphs

About 1 year old · traced to

Let GG be a planar graph, and let af(G)a_f(G) denote its fractional arboricity: the minimum ratio p/qp/q for which vertices can be assigned at least qq colors from a total of at most pp colors, with every color class inducing an acyclic subgraph. Bonamy–Kardos–Kelly–Postle conjecture. Every planar graph satisfies

af(G)≤2.a_f(G)\leq 2.

The paper's abstract states that this conjecture is refuted by a planar signed simple graph whose fractional balanced chromatic number is larger than 2; the construction also yields planar graphs with fractional arboricity exceeding 2.

References

Primary source

Reza Naserasr, Lan Anh Pham, Cyril Pujol and Huan Zhou, “Fractional balanced chromatic number and arboricity of planar (signed) graphs”, arXiv:2505.16808 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.