k-tuple colorings of the cartesian product of graphs

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

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2018 vol. 245 p. 177 - 182

0166-218X

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.