Conditional Coloring Of Graphs

The study on graph colorings plays a central role in graph theory. There are number of colorings of graphs. Conditional coloring of graphs is discussed in this paper. It was introduced recently. For k>0 and r>0, a proper (k,r)-coloring of graph G is a c : V(G) → (K|-) = {1,2...k} such that both of the following hold: if u,v∈V(G) are adjacent vertices in G, then c(u)≠c(v) and for any v∈K(G), |c(N(v))|≥min{d(v),r}. For fixed number r, the smallest k such that G has a proper (k,r)-coloring is the conditional chromatic number of G, denoted x_r(G). Using extension and adjustment of graphs we give a distance partition of G, obtain the upper bound of conditional coloring number of G and the graphs satisfying this bound. The main result is: x_r(G)≤Δ~2+1, equality holds if and only if G is Moore graphs.