An edge coloring of a graph G is woody if no cycle in G is monochromatic. The arboricity of a graph G, denoted by \({{\,\textrm{arb}\,}}(G)\) , is defined as the least number of colors needed for a woody coloring of G. Motivated by some recent higher-order generalizations of this parameter, we introduce here a new variant of arboricity based on the classical Whitney’s idea of broken circuits. A broken cycle in a graph G is any simple path in G obtained by deleting a single edge from a cycle in G. An edge coloring of G is strongly woody if no broken cycle in G is monochromatic. The least number of colors in a strongly woody coloring of G is denoted by \(\zeta (G)\) and called the strong arboricity of G. We prove that \(\zeta (G)\leqslant \chi _a(G)\) , where \(\chi _a(G)\) is the acyclic chromatic number of G, defined as the least number of colors in a proper vertex coloring avoiding a 2-colored cycle. This implies that \(\zeta (G)\leqslant 5\) , for any planar graph G, and \(\zeta (G)\leqslant 3\) , for any outerplanar graph. We conjecture that \(\zeta (G)\leqslant 4\) holds for all planar graphs and confirm this bound in the case of triangle-free planar graphs. We also prove that planar graphs with girth at least 13 satisfy \(\zeta (G)\leqslant 2\) . In general, \(\zeta (G)\leqslant 4({{\,\textrm{arb}\,}}(G))^2\) holds for an arbitrary graph G, but we suspect that the true upper bound is linear. The paper is concluded with some open problems.
