The Conditional Chromatic Number χ₃(G) Of Graphs

The study on graph colorings plays a central role in graph theory. Conditional coloring ofgraphs introduced recently is discussed in this paper. Fork＞0 and r＞0, a proper (k, r)—coloringofgraph G isamap c:V(G)→C(k)={1,2,…,k} such that (1)if uv∈E(G),thenc(u)≠c(v) and (2) for any v∈V(G), |c(N(v))|≥min{d(v), r}. The smallest integerk 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. discussedx₂ (G) and x_r(G). In this paper, x₃(G) of graphs withâ–³(G)≥3 is mainly investigated.Firstly, we give a upper bound of x₃(G) of graphs withâ–³(G)≥3: ifâ–³(G)≥3,then x₃(G)≤3A(G)+1, and the equality holds if G is Petersen graph (in this casex₃(G)=10). Then we raise a conjecture: for any G withâ–³(G)≥3, x₃(G)≤△(G)+5.Secondly, we show that for non—regular graphs G withâ–³(G)=3, 3—regular graphscontaining triangles and 3—regular graphs with |V(G)|≤10, x₃(G)≤△(G)+ 5, and the boundis the best possible; for G withâ–³(G)≥4, x₃(G)≤△(G)+5 if and only if for G withâ–³(G)≥4 andδ(G)=3, x₃(G)≤△(G)+5.