k-tuple chromatic number of the cartesian product of graphs

FLAVIA BONOMO; IVO KOCH; PABLO TORRES; MARIO VALENCIA-PABON

Electronic Notes in Discrete Mathematics

Elsevier

Año: 2015

1571-0653

A $k$-tuple coloring of a graph $G$ assigns a set of $k$ colors toeach vertex of $G$ such that if two vertices are adjacent, thecorresponding sets of colors are disjoint. The $k$-tuple chromaticnumber of $G$, $chi_k(G)$,  is the smallest $t$ so that there isa $k$-tuple coloring of $G$ using $t$ colors.  It is well knownthat $chi(G Box H) = max{chi(G),chi(H)}$. In this paper, weshow that there exist graphs $G$ and $H$ such that $chi_k(G BoxH) > max{chi_k(G),chi_k(H)}$ for $kgeq 2$. Moreover, we alsoshow that there exist graph families such that, for any $kgeq 1$,the $k$-tuple chromatic number of their cartesian product is equalto the maximum $k$-tuple chromatic number of its factors.