INVESTIGADORES
BONOMO flavia
congresos y reuniones científicas
Título:
k-tuple chromatic number of the cartesian product of graphs
Autor/es:
BONOMO, FLAVIA; KOCH, IVO; TORRES, PABLO; VALENCIA-PABON, MARIO
Lugar:
Fortaleza
Reunión:
Simposio; Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS); 2015
Resumen:
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 is a $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 Box H) > max{chi_k(G),chi_k(H)}$ for $kgeq 2$. Moreover, we also show that there exist graph families such that, for any $kgeq 1$, the $k$-tuple chromatic number of their cartesian product is equal to the maximum $k$-tuple chromatic number of its factors.