Article ID Journal Published Year Pages File Type
4651241 Discrete Mathematics 2007 9 Pages PDF
Abstract

Given non-negative integers r, s, and t  , an [r,s,t][r,s,t]-coloring   of a graph G=(V(G),E(G))G=(V(G),E(G)) is a mapping c   from V(G)∪E(G)V(G)∪E(G) to the color set {0,1,…,k-1}{0,1,…,k-1} such that |c(vi)-c(vj)|⩾r|c(vi)-c(vj)|⩾r for every two adjacent vertices vi,vjvi,vj, |c(ei)-c(ej)|⩾s|c(ei)-c(ej)|⩾s for every two adjacent edges ei,ejei,ej, and |c(vi)-c(ej)|⩾t|c(vi)-c(ej)|⩾t for all pairs of incident vertices and edges, respectively. The [r,s,t][r,s,t]-chromatic number  χr,s,t(G)χr,s,t(G) of G is defined to be the minimum k such that G   admits an [r,s,t][r,s,t]-coloring.This is an obvious generalization of all classical graph colorings since c   is a vertex coloring if r=1r=1, s=t=0s=t=0, an edge coloring if s=1s=1, r=t=0r=t=0, and a total coloring if r=s=t=1r=s=t=1, respectively.We present first results on χr,s,t(G)χr,s,t(G) such as general bounds and also exact values, for example if min{r,s,t}=0min{r,s,t}=0 or if G is a complete graph.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,