Bounds for B-coloring planar and outerplanar graphs

arXiv:2610.37497 · math.CO · Submitted 2026-10-27 · Read on arXiv

math.CO

Submitted: 2026-10-27

Updated: 2026-10-27

Comments: 21 pages, 5 figures

Journal ref: Discrete Math. 350 (2027), no. 2, Article No. 115426

DOI: 10.1016/j.disc.2026.115426

License: http://creativecommons.org/licenses/by/4.0/

The gist: A proper coloring of the edges of a graph is one in which every K 1,2 is totally multicolored.

Abstract

A proper coloring of the edges of a graph is one in which every K 1,2 is totally multicolored. A B-coloring is a coloring of the edges of G in which every K 1,2 and every K 2,2 is totally multicolored. In this paper, we improve two results by the authors and Gyárfás. The first shows that an outerplanar graph with maximum degree Δ can be B-colored with Δ,9 colors, improving a bound of Δ+1 and this is best possible up to the constant 9. The second shows that a planar graph with maximum degree Δ can be B-colored with 2Δ+4,22, improving a bound of 2Δ+8.

Related papers