Abstract:

       Conditional (k,r) coloring of a graph G is a map c:V(G)→{1,2,…,k}  for positive integers k and  r. It satisfies two conditions that if  u,v∈V(G)  are adjacent vertices in  G, then c(u)≠c(v), and that |c(N(v))|≥ min{|N(v)|,r} for any v∈V(G). The conditional chromatic number of a graph G,χ_r(G), is the smallest k that makes G have a proper(k,r)coloring. We address the conditional chromatic number of several special types of graphs when r is 3.

Key words: conditional coloring, conditional chromatic number, split graph, Hajós sum