k-tuple colorings of the Cartesian product of graphs

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

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 to each vertex of $G$ such that if two vertices are adjacent, the corresponding sets of colors are disjoint. The $k$-tuple chromatic number of $G$, $chi_k(G)$, is the smallest $t$ so that there isa $k$-tuple coloring of $G$ using $t$ colors. It is well known that $chi(G Box H) = max{chi(G),chi(H)}$. In this paper, we show that there exist graphs $G$ and $H$ such that $chi_k(G BoxH) > max{chi_k(G),chi_k(H)}$ for $k geq 2$. Moreover, we also show that there exist graph families such that, for any $k geq 1$,the $k$-tuple chromatic number of their Cartesian product is equal to the maximum $k$-tuple chromatic number of its factors.