MathDB

Fractional Albertson–Berman conjecture for planar graphs

Let GG be a planar graph, and let \fva(G)\fva(G) denote its fractional vertex-arboricity. Fractional Albertson–Berman conjecture. Every planar graph has fractional vertex-arboricity at most two, that is,

\fva(G)≤2.\fva(G)\leq 2.

This conjecture is a fractional analogue of the Albertson–Berman conjecture that every planar graph has an induced forest on at least half of its vertices. The paper notes that the best known general bound is \fva(G)≤5/2\fva(G)\leq 5/2, and that the conjectured bound would imply the known upper bound four for the fractional chromatic number by a new method.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, František Kardoš, Tom Kelly and Luke Postle, “Fractional vertex-arboricity of planar graphs”, arXiv:2009.12189 (2020).

fractional-vertex-arboricityinduced-forestsplanar-graphs

Progress summary

Refreshed
Open

The proposed universal bound has not been proved or disproved, and the best general estimate remains above the conjectured value.

The Fractional Albertson–Berman conjecture, stated in a 2020 paper, asserts that every planar graph satisfies fva(G)≤2\mathrm{fva}(G)\leq 2. It is the fractional analogue of the Albertson–Berman induced-forest conjecture from 1979.

Known results

  • Borodin’s acyclic 55-color theorem yields the general bound fva(G)≤5/2\mathrm{fva}(G)\leq 5/2.
  • The 2020 paper proves fva(G)≤2−1324\mathrm{fva}(G)\leq 2-\frac{1}{324} for planar graphs of girth at least 55.
  • The conjectured bound would imply fractional chromatic number at most 44 for planar graphs.

Current status (as of August 2026): The conjecture remains open; fva(G)≤5/2\mathrm{fva}(G)\leq 5/2 is known generally, with the stronger bound established only for planar graphs of girth at least 55.

Sources

Solutions 0

No solutions have been posted yet.