Conditional Coloring Of 3-regular Graphs

The study on graph colorings plays a central role in graph theory. Fork>0 and r>0, a proper (k, r)-coloring of graph G is a map c:V(G)→C(k)={\,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 X_r(G).The computation of X_r(G) is a difficult problem. Lai Hongjian etc. discussed X₂(G) and X_r(G), and offered an upper bound X_r(G)≤△²+1 . Lin Yue improved the upper bound and proved X_r(G)≤râ–³+1. Wang Junhua raised a conjecture that a graph G withâ–³(G)≥3 , except Petersen graph,has X₃(G)≤△(G)+5In this paper, X₃(G) of 3-regular graphs withâ–³A(G)≥3 is mainly investigated. Firstly,we proved that if a 3-regular graph with 10 vertexes, its conditional chromatic number has upper bound 8. Then we proved that if a 3-regular graph with 2 cycles have common edges, its conditional chromatic number has upper bound 8. And for a 3-regular graph G withconnectivity 1 or 2, X₃(G)≤8. Lastly, we made a deep discussion on the generalized Petersen graphs P(n, t). We proved X₃(P(n,t))≤8 except the Petersen graph. Moreover, if generalized Petersen graphs satisfying n(?)0(mod4) and (4,t)=1, then X₃(P(n, t))=4; and if generalized Petersen graphs satisfying n(?)0(mod5) and t(?)±1(mod5), then 4≤X₃(P(n, t))≤5.