[r, s, t]-Colorings of Graph Products

Research paper by Lyes Dekar, Brice Effantin, Hamamache Kheddouci

Indexed on: 13 Aug '13Published on: 13 Aug '13Published in: Graphs and Combinatorics


Let G =  (V, E) be a graph with vertex set V and edge set E. Given non negative integers r, s and t, an [r, s, t]-coloring of a graph G is a proper total coloring where the neighboring elements of G (vertices and edges) receive colors with a certain difference r between colors of adjacent vertices, a difference s between colors of adjacent edges and a difference t between colors of a vertex and an incident edge. Thus [r, s, t]-colorings generalize the classical colorings of graphs and can have applications in different fields like scheduling, channel assignment problem, etc. The [r, s, t]-chromatic number χr,s,t(G) of G is the minimum k such that G admits an [r, s, t]-coloring. In our paper we propose several bounds for the [r, s, t]-chromatic number of the cartesian and direct products of some graphs.