Fractional Balanced Chromatic Number and Arboricity of Planar (Signed) Graphs

ABSTRACT A balanced ‐coloring of a signed graph is an assignment of colors to each vertex of from a platter of colors, such that each color class induces a balanced set (a set that does not induce a negative cycle). The fractional balanced chromatic number of , denoted , is the minimum ratio such that has a balanced ‐coloring. This value is bounded by the fractional arboricity of , denoted , which is defined so that each color class induces an acyclic subgraph of . In this work we present an example of a signed planar simple graph of fractional balanced chromatic number greater than 2, in particular, refuting a conjecture of Bonamy, Kardoš, Kelly, and Postle suggesting that the fractional arboricity of planar graphs is bounded above by 2. By iterating the construction, we show that the supremum of the fractional balanced chromatic number of signed planar simple graphs is at least . Our method results in a construction of a planar graph on 34 vertices whose fractional arboricity is .