(r, s, t)-coloring of trees and bipartite graphs

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 function c from V ( G ) ∪ E ( G ) to the color set { 0 , 1 , … , k − 1 } such that | c ( v i ) − c ( v j ) | ≥ r for every two adjacent vertices v i , v j ∈ V , | c ( e i ) − c ( e j ) | ≥ s for every two adjacent edges e i , e j ∈ E , and | c ( v i ) − c ( e j ) | ≥ t for every vertex v i and its incident edge e j . Thus, an [ r , s , t ] -coloring is a generalization of the total coloring and the classical vertex and edge colorings of graphs. The [ r , s , t ] -coloring can have many applications in different fields like scheduling [A. Kemnitz, M. Marangio, [ r , s , t ] -colorings of graphs, Discrete Mathematics 307 (2) (2007) 199–207], channel assignment problem [F. Bazzaro, M. Montassier, A. Raspaud, ( d , 1 ) -total labelling of planar graphs with large girth and high maximum degree, Discrete Mathematics 307 (2007) 2141–2151], 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 give exact values (or bounds in one case) of the [ r , s , t ] -chromatic number of stars, for every positive r , s and t . We also provide exact values and some tight bounds of this parameter for trees and bipartite graphs.