Degeneracy bounds, stability, and a sharp gap for B-colorings
Abstract
A B-coloring of a graph is a proper edge-coloring in which every $4$-cycle is rainbow, and qB(G) denotes the minimum number of colors in such a coloring. Let Δ2(G) denote the maximum number of common neighbors of two distinct vertices of G. We prove that, for integers 1≤ d≤Δ, every finite simple d-degenerate graph G with Δ(G)≤Δ satisfies qB(G)≤ Δ+(d−1)Δ2(G)≤ dΔ. Consequently, dΔ is the exact maximum, with equality precisely for graphs containing Kd,Δ. More generally, if qB(G)≥ dΔ−s, where 0≤ s<Δ, then G contains Kd,Δ−s; if also s<d, then G has at least d−s vertices of degree Δ with the same open neighborhood. For Δ≥3, we further show that every K3,Δ-free 3-degenerate graph satisfies qB(G)≤3Δ−2; the example K3,Δ−1 shows that this bound is best possible up to one. For loopless multigraphs, we establish a sharp gap in the possible values of qB(G). For every integer Δ≥3, every finite loopless multigraph G with Δ(G)≤Δ satisfies qB(G)≤Δ(Δ−1) unless G has a component isomorphic to KΔ,Δ, in which case qB(G)=Δ2. The bound Δ(Δ−1) is attained by both KΔ,Δ−1 and KΔ,Δ−e. Consequently, among finite loopless multigraphs with maximum degree at most Δ, no value of qB(G) lies strictly between Δ2−Δ and Δ2.
Related
BibTeX
@misc{hu2026degeneracy,
title = {{Degeneracy bounds, stability, and a sharp gap for $B$-colorings}},
author = {Xiaoxue Hu and Jiangxu Kong and Yiqiao Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02845},
eprint = {2609.02845},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02845},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Degeneracy bounds, stability, and a sharp gap for B-colorings
AU - Xiaoxue Hu
AU - Jiangxu Kong
AU - Yiqiao Wang
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02845
UR - https://arxiv.org/abs/2609.02845
AB - A B-coloring of a graph is a proper edge-coloring in which every $4$-cycle is rainbow, and q_B(G) denotes the minimum number of colors in such a coloring. Let Δ_2(G) denote the maximum number of common neighbors of two distinct vertices of G. We prove that, for integers 1≤ d≤Δ, every finite simple d-degenerate graph G with Δ(G)≤Δ satisfies q_B(G)≤ Δ+(d−1)Δ_2(G)≤ dΔ. Consequently, dΔ is the exact maximum, with equality precisely for graphs containing K_d,Δ. More generally, if q_B(G)≥ dΔ−s, where 0≤ s<Δ, then G contains K_d,Δ−s; if also s<d, then G has at least d−s vertices of degree Δ with the same open neighborhood. For Δ≥3, we further show that every K_3,Δ-free 3-degenerate graph satisfies q_B(G)≤3Δ−2; the example K_3,Δ−1 shows that this bound is best possible up to one. For loopless multigraphs, we establish a sharp gap in the possible values of q_B(G). For every integer Δ≥3, every finite loopless multigraph G with Δ(G)≤Δ satisfies q_B(G)≤Δ(Δ−1) unless G has a component isomorphic to K_Δ,Δ, in which case q_B(G)=Δ^2. The bound Δ(Δ−1) is attained by both K_Δ,Δ−1 and K_Δ,Δ−e. Consequently, among finite loopless multigraphs with maximum degree at most Δ, no value of q_B(G) lies strictly between Δ^2−Δ and Δ^2.
ER -