Article ID Journal Published Year Pages File Type
4649140 Discrete Mathematics 2010 7 Pages PDF
Abstract

The square G2G2 of a graph GG is defined on the vertex set of GG in such a way that distinct vertices with distance at most 2 in GG are joined by an edge. We study the chromatic number of the square of the Cartesian product Cm□CnCm□Cn of two cycles and show that the value of this parameter is at most 7 except when (m,n)(m,n) is (3,3)(3,3), in which case the value is 9, and when (m,n)(m,n) is (4,4)(4,4) or (3,5)(3,5), in which case the value is 8. Moreover, we conjecture that whenever G=Cm□CnG=Cm□Cn, the chromatic number of G2G2 equals ⌈mn/α(G2)⌉⌈mn/α(G2)⌉, where α(G2)α(G2) denotes the maximum size of an independent set in G2G2.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,