B-coloring of grid graphs

Abstract

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árfás and Sárközy (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\ge 3$ are integers, we prove that $q_B(G)=4=\Delta (G)$ if both $m$ and $n$ are even and $G\ncong C_4\square C_{4k+2}$ for any integer $k\ge 1$, 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\ge 1$. 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\ge 2$ and $n\ge 2$, we have $q_B(C_{2n}\square P_m)=4$. For integers $m\ge 2$ and $n\ge 1$, 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.

arXiv comment18 pages, 4 figures, 9 tables