| |
|
|
Abstract: A face of an edge colored plane graph is called {\em rainbow} if all its edges receive distinct colors. The maximum number of colors used in an edge coloring of a connected plane graph $G$ with no rainbow face is called {\em the edge-rainbowness} of $G$. In this paper we prove that the edge-rainbowness of $G$ equals to the maximum number of edges of a connected bridge face factor $H$ of $G$, where a {\em bridge face factor} $H$ of a plane graph $G$ is a spanning subgraph $H$ of $G$ in which every face is incident with a bridge and the interior of any one face $f\in F(G)$ is a subset of the interior of some face $f'\in F(H)$. We also show upper and lower bounds on the edge-rainbowness of graphs based on edge connectivity, girth of the dual $G^*$ and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. Contact the authors: stanislav.jendrol@upjs.sk, jozef.miskuf@upjs.sk, roman.sotak@upjs.sk, erika.skrabulakova@upjs.sk Download PDF version of the preprint. |