B-coloring of $K_{2,t}$-free planar graphs

Source abstract

A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $Δ$ is $K_{2,Δ+1}$-free; hence the known $2Δ$ bound for planar graphs with $Δ\ge38$ (Kong et al., 2026) motivates our study of $K_{2,t}$-free planar graphs, where $t\ge2$ is an integer. We prove $q_B(G)=Δ(G)$ when $t=2$ and $Δ(G)\ge7$, or when $t\ge3$ and $Δ(G)\ge14(t-1)$. For $t\ge35$, the bound $q_B(G)\leΔ(G)+t-1$ holds regardless of $Δ(G)$; for every $t\ge2$, it also holds when $Δ(G)>428$. Finally, for every integer $k\ge1$, every $k$-degenerate $K_{2,t}$-free graph satisfies $q_B(G)\leΔ(G)+(k-1)\min\{t-1,Δ(G)\}$, with equality for $K_{k,t-1}$ when $k\ge2$ and $t-1\ge k$.