Coloring the Square of Products of Cycles and Paths

Abstract

The square $G^2$ of a graph $G$ is a graph with the same vertex set as $G$ in which two vertices are joined by an edge if their distance in $G$ is at most two. For a graph $G$, $\chi (G^2)$, which is also known as the distance two coloring number of $G$, is studied. We study coloring the square of grids $P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n$, cylinders $P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n$, and tori $C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n$. For each $m$ and $n$ we determine $\chi ((P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n{)}^2)$, $\chi ((P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n{)}^2)$, and in some cases $\chi ((C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n{)}^2)$ while giving sharp bounds to the latter. We show that $\chi ((C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n{)}^2)$ is at most $8$ except when $m=n=3$, in which case the value is $9$. Moreover, we conjecture that for every $m$ ($m\ge 5$) and $n$ ($n\ge 5$), we have $5\le \chi ((C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n{)}^2)\le 7$.