The ?-Bbackbone Coloring And B-coloring For Special Graphs

Let G be a graph,and H be a spanning subgraph of G.A function a:V(G)?{1,…,k} is a proper vertex coloring of G,and set of vertices colorized as i is denoted by Vi.If |f(u)-f(v)|?? holds for all edges uv?E(H),the proper vertex coloring a is called a ?-backbone coloring of(G,H).The ?-backbone coloring number of(G,H)is the smallest integer k for which there exists a ?-backbone k-coloring,denoted by BBC?(G,H).If exists a vertex v in each color class Vi,then {v}?Vj is not independent set,where i,j?{1,…,k} and i?j,and the proper vertex coloring a is called a b-coloring of G.The b-coloring number of a graph G,denoted by(?(G),is the maximal integer k such that G may have a b-coloring with k colors.This paper mainly studies the ?-backbone coloring and b-coloring of special graphs.The details are as follows.1.We study ?-backbone coloring number of a maximum of H?r(k)of the backbone H with a fixed maximum degree r on any k-color graph G.The specific results are as follows:(a)If k=r?0,then H?r(k)=(k-1)?+1;(b)If 0<k-r??,then H?r(k)=(?-1)r+k;(c)If r???k-r,then H?r(k)=(r+1)(k-r).2.We proven that ?-backbone coloring number of a maximum of T?(k)of the tree backbone T on any k-color graph G is(k-1)?+1.3.The b-coloring of three types of special operational graphs is studied,such as the b-coloring number of corona product(G o H)and edge corona product(G?H)for p-order graph G and q-order graph H,the b-coloring number of the same order graphs and any two complete graph H,and the b-coloring number of the generalized dictionary product of several kinds of special graphs.Some results are as follows:(a)If ?(H)+1?p-?(G)-1?q,then ?(G?H)=p;(b)If ?(H)+2?p-1?q+1,then ?(G?H)=p.4.When n?5 or k?27 the b-coloring number of the generalized Petersen graph P(n,k)is 4;otherwise,the b-coloring number of the Petersen graph P(5,2)is 3.The b-coloring number of the line graph L(P(n,k))of the generalized Petersen graph is 5.5.We prove that the b-coloring number of the infinite square,triangular and hexag-onal lattices are 5,7 and 4 on the plane,and the b-coloring number of n-dimensional infinite square lattices is(2n+1).