{"id":"arxiv/2609.02845","url":"https://arxiv.org/abs/2609.02845","tags":["math.CO"],"score":0,"title":"Degeneracy bounds, stability, and a sharp gap for $B$-colorings","domain":"math.CO","source":"arxiv","authors":["Xiaoxue Hu","Jiangxu Kong","Yiqiao Wang"],"reviews":0,"subject":"math.CO","summary":"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\\le d\\leΔ$, every finite simple $d$-degenerate graph $G$ with $Δ(G)\\leΔ$ satisfies $$q_B(G)\\le Δ+(d-1)Δ_2(G)\\le dΔ.$$ Consequently, $dΔ$ is the exact maximum, with equality precisely for graphs containing $K_{d,Δ}$. More generally, if $q_B(G)\\ge dΔ-s$, where $0\\le s<Δ$, then $G$ contains $K_{d,Δ-s}$; if also $s<d$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}