Bounds for B-coloring planar and outerplanar graphs
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$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.37497
curl -X POST /api/v1/records/arxiv/2610.37497/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.37497/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'