Autor(es)

Flavia Bonomo and Ivo Koch and Pablo Torres and Mario Valencia-Pabon

URL Pública

Abstract

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, χ k (G), is the smallest t so that there is a k-tuple coloring of G using t colors. It is well known that χ (G□ H)= max {χ (G), χ (H)}. In this paper, we show that there exist graphs G and H such that χ k (G□ H)> max {χ k (G), χ k (H)} for k≥ 2. Moreover, we also show that there exist graph families such that, for any k≥ 1, the k-tuple chromatic number of their Cartesian product is equal to the maximum k-tuple chromatic number of its factors.