PreprintCC BY 4.0arXiv
Bounds for B-coloring planar and outerplanar graphs
Abstract
A proper coloring of the edges of a graph is one in which every K1,2 is totally multicolored. A B-coloring is a coloring of the edges of G in which every K1,2 and every K2,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 max{Δ,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 max{2Δ+4,22}, improving a bound of 2Δ+8.
Versions
Related
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
- Frugal coloring in planar graphs with maximum degree 4 and 5
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- B-coloring of K2,t-free planar graphs
BibTeX
@misc{martin2026bounds,
title = {{Bounds for B-coloring planar and outerplanar graphs}},
author = {Ryan R. Martin and Miklós Ruszinkó and Gábor N. Sárközy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37497},
eprint = {2610.37497},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37497},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bounds for B-coloring planar and outerplanar graphs
AU - Ryan R. Martin
AU - Miklós Ruszinkó
AU - Gábor N. Sárközy
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37497
UR - https://arxiv.org/abs/2610.37497
AB - 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 max{Δ,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 max{2Δ+4,22}, improving a bound of 2Δ+8.
ER -