Coloring the square of the Cartesian product of two cycles (Q708380): Difference between revisions

The \textit{square} \(G^2\) of a graph \(G\) is given by \(V(G^2)=V(G)\) and \(\{u,v\} \in E(G^2)\) if and only if \(\{u,v\} \in E(G)\) or \(u\) and \(v\) have a common neighbour. The Cartesian product \(G \square H\) of given graphs \(G\) and \(H\) is the graph with vertex set \(V(G)\times V(H)\) where two vertices \((u_1, v_1)\) and \((u_2, v_2)\) are adjacent if and only if either \(u_1=u_2\) and \(\{v_1,v_2\}\in E(H)\) or \(v_1=v_2\) and \(\{u_1,u_2\}\in E(G)\). It is shown that the chromatic number of the Cartesian product \(C_m\square C_n\) of two cycles is at most 7 except when \((m,n)\) is \((3, 3)\), in which case the value is 9, and when \((m, n)\) is \((4, 4)\) or \((3, 5)\), in which case the value is 8. Moreover, it is conjectured that whenever \(G=C_m\square C_n\), the chromatic number of \(G^2\) equals \(\lceil mn/ \alpha(G^2)\rceil\), where \(\alpha(G^2)\) denotes the maximum size of an independent set in \(G^2\).