On B-Colorings in Planar Graphs

Abstract

Gyárfás and Sárközy [Studia Sci. Math. Hungar., 2023] defined a B-coloring of a graph to be a proper coloring of the edge set in which any $C_4$ is totally multicolored. Let $q_B(G)$ denote the minimum number of colors sufficient for a B-coloring of a graph $G$. In this paper, we prove that any planar graph $G$ with $\Delta =\Delta (G)$ and ${\Delta }_2={\Delta }_2(G)$ has $q_B(G)\le \Delta +\max \{{\Delta }_2,38\}$, refining a bound by Kong, Wang, and Zheng [J. Graph Theory, 2026].

7 pages, 2 figures