Star Edge-Coloring of Square Grids

NEW

Problem: Reconstructed statement: for finite simple graphs, let $\chi'_{\mathrm{st}}(G)$ be the minimum number of colors in a proper edge-coloring of $G$ with no bichromatic path or cycle of length $4$. The conjecture asks whether

This is exactly the supplied Conjecture 2.

Result: The conjecture is true. In fact, one may take $K=36$ and $n=12$ for every $m\ge36$.

Use vertices $(i,j)\in \mathbb Z_{13}\times\mathbb Z_{12}$. Let $H_{i,j}$ color edge $(i,j)(i+1,j)$, and $V_{i,j}$ color edge $(i,j)(i,j+1)$. The following rows are $j=0,\dots,11$, columns $i=0,\dots,12$, with colors $0,\dots,5$.

$H$:

0541025410341
4203450243103
0432014320532
3105340135205
0351023510451
5204530254104
0542015420342
4103450143203
0431024310531
3205340235105
0352013520452
5104530154204

$V$:

2315231305255
5151523151421
1524152504144
4242415242312
2413241403233
3131324131521
1325132305155
5252513252412
2514251504244
4141425141321
1423142403133
3232314232512

A direct finite check gives:

1. at every vertex the four incident edge-colors are distinct;
2. for every four-edge path or cycle $e_1e_2e_3e_4$, not both $c(e_1)=c(e_3)$ and $c(e_2)=c(e_4)$.

Thus this is a star $6$-edge-coloring of $C_{13}\square C_{12}$. Moreover, columns $0,1,2,3$, with the wrap edge from column $3$ to column $0$ colored by $H_{12,j}$, pass the same check, so this coloring includes a star $6$-edge-coloring of $C_4\square C_{12}$.

By the standard concatenation lemma for included cycle colorings, this yields a star $6$-edge-coloring of

for all $a,b\ge0$. Since $\gcd(4,13)=1$, every $m\ge36$ has the form $m=4a+13b$. Therefore

The known lower bound $\chi'_{\mathrm{st}}(C_m\square C_n)\ge6$ for $m,n\ge3$ gives equality.

Verification audit: the statement proved is stronger than the conjecture, uses $n=12$ uniformly, and introduces no extra hypothesis beyond $m\ge36$.

Citation: Holub, Lužar, Mihaliková, Mockovčiaková, Soták, “Star Edge-Coloring of Square Grids,” Applied Mathematics and Computation 391 (2021), 125741; arXiv:2005.02864. Used for the lower bound and concatenation lemma.