Coloring the square of the Cartesian product of two cycles

Details Coloring the square of the Cartesian product of two cycles Coloring the square of the Cartesian product of two cycles

2009-06-05

arxiv.org/abs/0906.1126v3

Computer Science

Discrete Mathematics

Scientific paper

The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ in such a way that distinct vertices with distance at most two in $G$ are joined by an edge. We study the chromatic number of the square of the Cartesian product $C_m\Box C_n$ of two cycles and show that the value of this parameter is at most 7 except when $m=n=3$, in which case the value is 9, and when $m=n=4$ or $m=3$ and $n=5$, in which case the value is 8. Moreover, we conjecture that whenever $G=C_m\Box C_n$, the chromatic number of $G^2$ equals $\lceil mn/\alpha(G^2) \rceil$, where $\alpha(G^2)$ denotes the size of a maximal independent set in $G^2$.

Affiliated with

Also associated with

No associations

Rating

Coloring the square of the Cartesian product of two cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coloring the square of the Cartesian product of two cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coloring the square of the Cartesian product of two cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-522663