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 $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\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)=\Delta(G)$ when $t=2$ and $\Delta(G)\ge7$, or when $t\ge3$ and $\Delta(G)\ge14(t-1)$. For $t\ge35$, the bound $q_B(G)\le\Delta(G)+t-1$ holds regardless of $\Delta(G)$; for every $t\ge2$, it also holds when $\Delta(G)>428$. Finally, for every integer $k\ge1$, every $k$-degenerate $K_{2,t}$-free graph satisfies $q_B(G)\le\Delta(G)+(k-1)\min\{t-1,\Delta(G)\}$, with equality for $K_{k,t-1}$ when $k\ge2$ and $t-1\ge k$.
A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle is rainbow. Let $q_B(G)$ be the minimum number of colors in such a coloring. Gy\'arf\'as and S\'ark\"ozy (2023) determine $q_B(G)$ when $G=P_m\square P_n$ is a rectangular grid. In this paper, we completely determine $q_B(G)$ for cylindrical and torus grid graphs $G$. For a torus grid $G=C_m\square C_n$, where $m,n\ge3$ are integers, we prove that $q_B(G)=4=\Delta(G)$ if both $m$ and $n$ are even and $G\not\cong C_4\square C_{4k+2}$ for any integer $k\ge1$, and that $q_B(G)=5=\Delta(G)+1$ if at least one of $m,n$ is odd or $G\cong C_4\square C_{4k+2}$ for some integer $k\ge1$. For a cylindrical grid $G=C_s\square P_m$, $q_B(G)$ also depends on the parity of $s$ and the length of $P_m$. For integers $m\ge2$ and $n\ge2$, we have $q_B(C_{2n}\square P_m)=4$. For integers $m\ge2$ and $n\ge1$, we have $q_B(C_{2n+1}\square P_m)=4$ if $2\le m\le n$, whereas $q_B(C_{2n+1}\square P_m)=5$ if $m\ge n+1$. In higher dimensions, we discuss the B-coloring of discrete torus and $\ell$-cylindrical grid, obtaining some exact results and certain bounds.
Zheng Jiang, Jia-Ao Li· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
