Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649140 | Discrete Mathematics | 2010 | 7 Pages |
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
Éric Sopena, Jiaojiao Wu,