pith. sign in

arxiv: 0906.1126 · v3 · submitted 2009-06-05 · 💻 cs.DM

Coloring the square of the Cartesian product of two cycles

classification 💻 cs.DM
keywords squarevaluealphacartesiancasechromaticcyclesnumber
0
0 comments X
read the original abstract

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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.