Bounds for B-coloring planar and outerplanar graphs
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality