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 $Δ=Δ(G)$ and $Δ_2=Δ_2(G)$ has $q_B(G)\leqΔ+\max\{Δ_2,38\}$, refining a bound by Kong, Wang, and Zheng [J. Graph Theory, 2026].

Disclosure

“thor would also like to thank Yuping Gao for alerting him to the publication of [8], giving inspiration for this paper. The example of K1,1,∆−1 which established that qB (G) > max {χ′ (G), 2∆2 (G)} was found with the assistance of M365 Copilot based on the GPT-5 chat model, accessed 28 July 2026. References [1] O. V. Borodin, H. J. Broersma, A. N. Glebov, and J. van den Heuvel. Stars and bunches in planar graphs. part II: General planar graphs and colourings. CDAM Resear”

PDF page 6

Classification

Suggesting mathematical examples or conjectures

Multiplier

6

Verified

2026-08-23T05:08:27.363678Z

Structural counts