ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
k-tuple colorings of the cartesian product of graphs
Autor/es:
FLAVIA BONOMO; MARIO VALENCIA-PABON; PABLO TORRES; IVO KOCH
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2018 vol. 245 p. 177 - 182
ISSN:
0166-218X
Resumen:
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.