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 $q_B(G)$ denotes the minimum number of colors in such a coloring. Let $\Delta_2(G)$ denote the maximum number of common neighbors of two distinct vertices of $G$. We prove that, for integers $1\le d\le\Delta$, every finite simple $d$-degenerate graph $G$ with $\Delta(G)\le\Delta$ satisfies $$q_B(G)\le \Delta+(d-1)\Delta_2(G)\le d\Delta.$$ Consequently, $d\Delta$ is the exact maximum, with equality precisely for graphs containing $K_{d,\Delta}$. More generally, if $q_B(G)\ge d\Delta-s$, where $0\le s<\Delta$, then $G$ contains $K_{d,\Delta-s}$; if also $s<d$, then $G$ has at least $d-s$ vertices of degree $\Delta$ with the same open neighborhood. For $\Delta\ge3$, we further show that every $K_{3,\Delta}$-free 3-degenerate graph satisfies $q_B(G)\le3\Delta-2$; the example $K_{3,\Delta-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 $\Delta\ge3$, every finite loopless multigraph $G$ with $\Delta(G)\le\Delta$ satisfies $$q_B(G)\le\Delta(\Delta-1)$$ unless $G$ has a component isomorphic to $K_{\Delta,\Delta}$, in which case $q_B(G)=\Delta^2$. The bound $\Delta(\Delta-1)$ is attained by both $K_{\Delta,\Delta-1}$ and $K_{\Delta,\Delta}-e$. Consequently, among finite loopless multigraphs with maximum degree at most $\Delta$, no value of $q_B(G)$ lies strictly between $\Delta^2-\Delta$ and $\Delta^2$.