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).