B-colorings of planar and outerplanar graphs

Abstract

A coloring of the edges of a graph $G$ in which every $K_{1,2}$ is totally multicolored is known as a proper coloring and a coloring of the edges of $G$ in which every $K_{1,2}$ and every $K_{2,2}$ is totally multicolored is called a B-coloring. In this paper, we establish that a planar graph with maximum degree $\hat{I}”$ can be B-colored with $\max \{2\hat{I}”,32\}$ colors. This is best-possible for large $\hat{I}”$ because $K_{2,\hat{I}”}$ requires $2\hat{I}”$ colors. In addition, there is an example with $\hat{I}”=4$ that requires $12$ colors. We also establish that an outerplanar graph with maximum degree $\hat{I}”$ can be B-colored with $\max \{\hat{I}”,6\}$ colors. This is almost best-possible because $\hat{I}”$ colors are necessary and there is an example with $\hat{I}”=4$ that requires $5$ colors.

There is a fundamental error in the major proofs in this manuscript. The proofs are based on an induction on the number of edges, however, this induction removes some constraints and makes the proof by induction false. The authors were not able to find a way to repair the error