The Incidence Chromatic Number of Toroidal Grids

Original · EN

An incidence in a graph G is a pair (v,e) with v ∈ V(G) and e ∈ E(G), such that v and e are incident. Two incidences (v,e) and (w,f) are adjacent if v=w, or e=f, or the edge vw equals e or f. The incidence chromatic number of G is the smallest k for which there exists a mapping from the set of incidences of G to a set of k colors that assigns distinct colors to adjacent incidences. In this paper, we prove that the incidence chromatic number of the toroidal grid Tₘ,ₙ=Cₘ Cₙ equals 5 when m,n ≡ 0 5 and 6 otherwise.