The incidence chromatic number of toroidal grids (Q2860861)

An incidence in a simple graph \(G\) is an ordered pair \((v,e)\) where \(v\in V(G)\) is an end vertex of the edge \(e\in E(G)\). Two incidences \((v,e)\) and \((w,f)\) are then adjacent if \(v=w\), or \(e=f\), or the edge \(vw\) equals either \(e\) or \(f\). The incidence chromatic number of \(G\) is then the smallest natural number \(k\) such that there is a mapping from the set of all incidences of \(G\) to the set of \(k\) colors such that no two adjacent incidences receive the same color. The Cartesian product \(G\square H\) of simple graphs \(G\) and \(H\) is the graph with vertex set \(V(G)\times V(H)\) and 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_1v_2\in E(H)\), or \(v_1=v_2\) and \(u_1u_2\in E(G)\).NEWLINENEWLINENEWLINE The main result of this paper is to show that the incidence chromatic number of the toroidal grid \(C_m\square C_n\) (the Cartesian product of the \(m\)-cycle and the \(n\)-cycle) is 5 when \(m,n \equiv 0\pmod 5\) and is 6 otherwise.