Edge-coloring of plane graphs with many colors on faces

Abstract

For a fixed positive integer $p$, a coloring of the edges of a multigraph $G$ is called $p$-acyclic coloring if every cycle $C$ in $G$ contains at least $\min\{|C|,p+1\}$ colors. The least number of colors needed for a $p$-acyclic coloring of $G$ is the $p$-arboricity of $G$. This type of coloring was introduced by Ne\v set\v ril, Ossona de Mendez, and Zhu in 2014. From a result of Bartnicki et al. (2019) it follows that there are planar graphs with unbounded $p$-arboricity. In this note we improve a result of Bartnicki et al. on $p$-arboricity of planar graphs with large girth. In addition, we relax the definition of $p$-arboricity for plane multigraphs in sense that the requirement is not for all cycles but only for facial ones, and we show that the smallest number of colors needed for such a coloring is a constant (depending on $p$ only).