Metraipolis › archive › dc_b2cafa62a0dc
B-coloring of grid graphs — arXiv:2608.21774
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.21774
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T08:29:54.000Z
- SHA-256 of the archived text
1884b0fe1f94bce5d9992c49bde91af9396ee3e0b003a59d8a15ee3034f0eae6- Stable URL of this page
https://metraipolis.com/documento/dc_b2cafa62a0dc
How to cite
B-coloring of grid graphs — arXiv:2608.21774 — arXiv (en), https://arxiv.org/abs/2608.21774 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b2cafa62a0dc (Metraipolis archive dc_b2cafa62a0dc, sha256 1884b0fe1f94bce5d9992c49bde91af9396ee3e0b003a59d8a15ee3034f0eae6)
BibTeX
@misc{dcb2cafa62a0dc,
title = {B-coloring of grid graphs — arXiv:2608.21774},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.21774},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b2cafa62a0dc; sha256 1884b0fe1f94bce5d9992c49bde91af9396ee3e0b003a59d8a15ee3034f0eae6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.21774. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.21774 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T08:27:54.389Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).