The Upper Bound Of Conditional Coloring Of Graphs

The study on graph colorings plays an essential role in graph theory. In this paper, conditional coloring and dynamic coloring of graphs are studied. These colorings have been introduced and researched in recent years. For k > 0 andr > 0 ,a proper (k, r) - coloring of graph G is a map c:V(G)(?)C(k) = {1, 2,…, k} .such that (1)if uv∈E(G), then c(u)≠c(v) and (2) for any v∈V(G),|c(N(v))|≥min{d(v), r} .The smallest integer k for which a graph has a proper (k, r) - coloring is the r -conditional chromatic number , denoted byχ_r(G). The computation ofχ_r(G) is a NP problem. So far, thebest upper bound of conditional coloring isχ_r(G)≤△~2 (G) +1 .In the first part of thispaper, we get a conditional graph of simple graphs through an algorithm , discuss the relationship between the chromatic number of conditional graph and the chromatic number of original graph, and then find two upper bounds of conditional coloring:(1)χ_r(G)≤r△+ 1 and (2)χ_r(G)≤1+rδ'.With respect of the conditionalcoloring, the study of dynamic coloring is more mature, and some good conclusions have been obtained. In the second part, we get an induced graph by defining another algorithm, and use it to study the upper bounds of dynamic chromatic number of planar graphs. Finally, we give a new proof of an important conclusion: If G is planar, thenχ_d(G)≤5.