k-tuple chromatic number of the cartesian product of graphs

Flavia Bonomo (1, 2) , Ivo Koch (3) , Pablo Torres (2, 4) , Mario Valencia-Pabon (5, 6)

1 Departamento de Computación [Buenos Aires]
2 CONICET - Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
3 UNGS - Universidad Nacional de General Sarmiento [Los Polvorines, Buenos Aires]
4 Universidad Nacional de Rosario [Santa Fe]
5 ORPAILLEUR - Knowledge representation, reasonning
6 LIPN - Laboratoire d'Informatique de Paris-Nord

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 χ(GH) = max{χ(G), χ(H)}. In this paper, we show that there exist graphs G and H such that χ k (GH) > 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.

Mots clés: k-tuple colorings; Cartesian product of graphs; Kneser graphs; Cayley graphs; Hom-idempotent graphs

Domaines: Mathématiques [math]

Flavia Bonomo, Ivo Koch, Pablo Torres, Mario Valencia-Pabon. k-tuple chromatic number of the cartesian product of graphs. 2014. ⟨hal-01103534⟩