图的邻点可区别的全染色
|
摘要
染色问题是图论研究的经典领域，是图论研究中一个很活跃的话题．染色问题及许多图理论均源自四色问题的研究，随着染色问题在现实中被广泛应用，各类染色问题被相继提出并加以发展，研究．
图G的一个正常k-染色是将k种颜色分配给G的顶点集V(G)使得两相邻顶点的颜色不同．定义色数为χ(G)=min{k|图G有k-染色}．类似的，图G的一个正常k-边染色是将k种颜色分配给G的边集E(G)．使得有公共端点的两边的颜色不同，边色数χ′(G)=min{k|图G有k-边染色}.
全染色的概念是对点染色和边染色的推广，是图染色的一个传统问题，由Vizing(1964)．Behzad(1965)各自独立提出．图的全染色是对图的点，边进行染色使得相邻或相关联的元素颜色不同．在全染色的基础上张忠辅提出了邻点可区别的全染色概念并给出了相应的猜想和两个引理．
张忠辅给出的邻点可区别的全染色定义是这样的：
设图G(V，E)为阶至少为2的简单连通图，k为正整数．函数f是从V(G)∪E(G)到C={1，2，…，k)(也记作；C=[k])的一个映射：对于任意顶点u∈V(G)，记C(u)={f(u)}∪{f(uv)|uv∈E(G))，(?)(u)=C-C(u)：
(1)对任意边uv，vw∈E(G)，且u≠w，有f(uv)≠f(vw)；
(2)对任意边uv∈E(G)，且u≠v，有f(u)≠f(v)，f(u)≠f(uv)，f(uv)≠f(v)：
(3)对于任意边uv∈E(G)，且u≠v，有C(u)≠C(v)．
若满足条件(1)，(2)．则称f为图G的一个正常k-全染色(简记为k-TC)．
若满足条件(1)，(2)，(3)，则称f为图G的一个k-邻点可区别的全染色(简记为k-AVDTC).
图G的全色数为χ_T(G)=min{k图G有k-TC}．
图G的邻点可区别的全色数为χ_(at)(G)=min{k|图G有k-AVDTC}．
下面两个关于邻点可区别的全染色的引理：
对任意阶为n(n=|V(G)|≥2)的简单连通图G，邻点可区别全色数χ_(at)(G)存在，并且χ_(at)(G)≥△(G)+1．
若图G(V，E)有两相邻的最大度顶点，则χ_(at)(G)≥△(G)+2．
张忠辅在文献中给出了关于邻点可区别全染色的猜想：
对任意阶为n(n=|V(G)|≥2)的简单连通图G．有χ_at(G)≤△(G)+3．
对于路，圈，完全图，完全二部图，星，扇，轮，树等特殊图类目前已得出了其具体的邻点可区别的全色数，并且满足上述猜想．关于上述特殊图的Mycielshi图，联图和乘积图的邻点可区别的全色数已有一些结果．另外，Petersen图，Hewood图，Tomassen图及W_n的Hajós sum图的邻点可区别的全染色也已得到一些结果．
确定一个给定图的邻点可区别的全色数是NP-困难的，本文对一些特殊图及在某些图运算下的图的邻点可区别的全染色进行了研究．
在本文我们得到如下结论：
图的插入运算：已知图G，H且有|V(G)|=|E(H)|，图G插入H是指用G的所有顶点一一对应地剖分H的所有边，原G中的边不变．
点扩充图：图G的v(H)点扩充图是指将G的某顶点v用图H代替，但v的每个邻点只分别与H的一点相邻，即：v的每个邻点的度不变．
Hajós sum：两个点不交的图G_1，G_2的Hajós sum：G=(G_1，x_1y_1)+(G_2，x_2y_2)将x_1x_2粘合为一点x，删掉边x_1y_1，x_2y_2增加边y_1y_2所得．其中x_1y_1，x_2y_2分别是G_1，G_2的边．
点分裂图：图G的点分裂图是指将G的每个顶点用两个独立的点代替得到的图，记为G[I_2]．
第一类图：若G存在相邻最大度点且χ_(at)(G)=△(G)+2，则称G为第一类图．
第二类图：若G存在相邻最大度点且χ_(at)(G)=△(G)+3，则称G为第二类图．
定理2．1．1将K_n插入G_n所得图在文献中记作S_n．此处我们仍保持原记法，其中V(C_n)={u_1，u_2，…，u_n)；V(K_n)={v_1，v_2，…，v_n)；V(S_n)={v_1，v_2，…，v_n，u_1，u2，…，u_n)；E(S_n)={v_iv_j，v_iu_i；i，j=1，…，n)∪{u_nv_1，u_1v_2，…，u_(n-1)v_n)；则：χ_(at)(S_n)=△(S_n)+2=n+3；(n≥3)．
定理2．1．2 W_n插入C_(n+1)中所得图记为G其中V(C_(n+1))={u_1，…，u_(n+1))，V(W_n)={v_1，…，v_n，w}，V(G)={u_1，…，u_(n+1)，v_1，…，v_n，w}，E(G)={wv_i，v_iv_(i+1)，wu_(n+1)，u_iv_i，v_iu_(i+1)|i=1，…，n：这里用v_(n+1)表示v_1}；则：χ_(at)(G)=△(G)+1=n+3，(n≥4)．
定理2．1．3圈C_n，V(C_n)={u_1，…，u_n)图H，V(H)={v_1，…，v_n)将H插入C_n所得图记为G′，V(G′)={u_1，…，u_n；v_1，…，v_n}，E(G′)={u_iv_i，v_iu_(i+1)，(i=1，…，n；用u_(n+1)表示u_1)∪E(H)：若H满足邻点可区别的全染色猜想，即：χ_(at)(H)≤△(H)+3，则：G′也满足χ_(at)(G′)≤△(G′)+3．
定理2．2．1图P~n(V.E)：V={u，v，w，v_1，v_2，…，v_n)：E={uv_i，vv_i，vw，(i=1，2，…n)；v_iv_(i+1)，(i=1，…，n-1))．则：
定理2．2．2令G_2表示P~n的u(K_n)扩充图，V(P~n)={u，v，w，v_1，v_2，…，v_n}；E(P~n)={uv_i，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1)}；V(K_n)={u_1，…，u_n}对于u_i∈K_nv_i∈P~n，(i=1，…，n)有：u_iv_i∈E(G_2)，(i=1，…，n)，则有：
定理2．2．3 H_1为P~n的一个u(S_n)点扩充图，V(S_n)={v′_1，v′_2，…，v′_n，u′_1，u′_2，…，u′_n}；E(S_n)={v′_iv′_j，v′_iu′_i：i，j=1，…，n}∪{u′_nv′_1，u′_1v′_2，…，u′_(n-1)v′_n}；V(P~n)={u，u，w，v_1，v_2，…，v_n)：E(P~n)={uv_i，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1)}对u′_i∈S_n，v_i∈P~n连接u′_i，v_i．(i=1，…，n)：则：χ_(at)(H_1)=n+3．
定理2．2．4令H_2为P~n的另一个u(S_n)点扩充图，对v′_i∈Sn，V(S_n)={v_1，v_2，…，v_n，u_1，u_2，…，u_n}；E(S_n)=(v_iv_j，v_iu_i；i，j=1，…，n}∪{u_nv_1，u_1v_2，…，u_(n-1)u_n}：V(P~n)={u，v，w，v_1，v_2，…，v_n}：E(P~n)={uv_i，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1))；对于v_i∈P~n连接v′_i，v_i，(i=1，…，n)，则：χ_(at)(H_2)=n+4．
定理2．2．5图G，V(G)={u_1，…，u_n}：P~n，V(P~n)={u，v，w，v_1，v_2，…，v_n)：E(P~n)={uv_1，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1))且4≤χ_(at)(G)=k≤△(G)+3，设H是P~n的u(G)扩充图，(其中对于v_i∈P~n，u_i∈G(i=1，…，n)有v_iu_i∈H)，若G满足邻点可区别的全染色猜想，即：χ_(at)(G)≤△(G)+3：则：χ_(at)(H)≤△(H)+3．
定理2．3．1记(P~n，uv_1)+((P)~n，u′v′_1)=G，则
定理2．3．2记(P~n，vv_n)+((?)~n，v′v′_n)=G′：则：χ_(at)(G′)=△(G′)+1=2n+1．
定理2．3．3令H=(S_n，u_1v_1)+(S′_m，u′_1v′_1)；则：χ_(at)(H)=max{χ_(at)(S_n)，χ_at(S′_m)}．
定理2．4．1 P_n是路，则n≠3时，P_n是第一类图，则P_n[I_2]也是第一类图．
定理2．4．2 F_n是扇，则n≥4时，F_n分裂后满足χ_(at)(F_n[I_2])=△(F_n[I_2])+1．
定理2．4．3 W_n是轮，则n≥4时，W_n分裂后满足χ_(at)(W_n[I_2])=△(W_n[I_2])+1．
定理2．5．1由图S_n，C_n~1，C_n~2，C_n~3我们得到新图H′，其中V(S_n)={v_1，v_2，…，v_n，u_1，u_2，…，u_n)；V(C_n~1)={v_1~1，…，v_n~1)：V(C_n~2)={v_1~2，…，v_n~2)；V(C_n~3)={v_1~3，…，v_n~3)；V(H′)=V(S_n)∪V(C_n~1)∪V(C_n~2)V(C_n~3)；E(H′)=E(S_n)∪E(C_n~1)∪E(C_n~2)∪E(C_n~3)∪{v_i~1v_i，v_i~2u_i，v_i~3v_i~1；v_i~j∈C_n~j；u_i，v_i∈S_n；|i=1，…，n，j=1，2，3)；则：χ_(at)(H′)=n+4，(n≥4)．
定理2．5．2令G_1表示P~n的顶点u用图P_2代替所得到的图，其中P_2的顶点为{u′，u″}，u′v_i，u″v_i，(i=1，…，n)均为G_1的边，则
定理2．5．3设G为简单连通图且△(G)≥4，V(G)={v_1，…，v_n)，对G做如下操作：若v_iv_j∈E(G)则添加点u_k且连接u_kv_i，u_kv_j，如此得到的新图记做H，若G满足邻点可区别的全染色猜想即：χ_(at)(G)≤△(G)+3，则H也满足：χ_(at)(H)≤△(H)+3．
The coloring problem is one of primary fields in the study of graph theories. The coloring problem and someother graph theories are all from the study of the celebrated four color problem. With the application of the coloring problem some scholars presented and studied a few coloring problem with different restriction.
A proper k-coloring of graph G is an assignment of k colors to each vertiex in such a way that adjacent vertices have distinct colors.Difine the chromatic number of G asχ(G) = min{k|graph G has k - coloring s}. Similar,a proper k-edge-coloring of graph G is an assignment of k colors to each edge so that no two adjacent edges have the same color.The edge-chromatic number is defined asλ′(G) = min{k|graph G has k - edge - colorings}.
The totle coloring is a generalization of the coloring and the edge coloring.It's a traditional coloring problem and was introduced by Vizing(1964) and independently Behzad(1965).the total coloring is defined as all of vertices and edges of the graph are colored in such a way that no two adjacent or incident elements are colored the same.On the basis of the total coloring,Zhang Zhongfu presented the concept of the concept of the adjacent vertex-distinguishing total colorings and gave the conjecture and two results.
The definition of adjacent vertex-distinguishing total coloring by Zhang Zhongfu is as follows : Let G(V,E) is a simple and connected graph of which the order is at least 2,k is an positive integer and f is the mapping from V(G)∪E(G) to C = {1,2,…,k}orC[k].
For any vertex u∈V(G) , denote C(u) = {f(u)}∪{f(u,v)|uv∈E(G)} . (?)(u) = C- C(u) .
(1) For any edge uv , vw∈E(G) , and u≠w,there is f(uv)≠f(vw) .
(2) For any edge uv∈E(G) ,and u≠v,there is f(u)≠f(v),f(u)≠f(uv), f(uv)≠f(v) .
(3) For any edge uv∈E(G) , and u≠v, there is C(u)≠C(v) .
If (1) , (2) are satisfied , then f is called a k-total coloring of graph G(in brief, it is noted as k-TC) .
If (1), (2) , (3) are satisfied , then f is called a k-adjacent vertex-distinguishing total coloring of graph G (in brief. it is noted as k-AVDTC) .
The total chromatic number of G isχ_T (G)= min{k|G has k-TC}.
The adjacent vertex-distinguishing total chromatic number of G isλ_(at)(G) = min{k| G has k-AVDTC}.
The following results about adjacent vertex-distinguishing total coloring are right . apparently .
For a simple connected graph G of order n (n = |V(G)|≥2) , adjacent vertex-distinguishing total chromatic numberχ_(at)(G) exist , andχ_(at)(G)≥△(G) + 1.
If G(V,E) has two adjacent maximum degree vertices , thenχ_(at)(G)≥△(G) + 2.
The following conjecture is proposed by Zhang Zongfu in :
For a simple connected graph G of order n (n = |V(G)|≥2) , thenχ_(at)(G)≤△(G) + 3.
The adjacent vertex-distinguishing total chromatic number of some graphs such as path,circle,complete graph, 2-complete graph . star . fan . wheel and tree have been abtained. We also have obtained the adjacent vertex-distinguishing total chromatic number of the Mycielski graph,link graph the Cartesian product graph,Petersen graph,Heawood graph Tomassen graph,the Haj(o|¨)s sum of W_n,etc. These results are satisfied the conjecture .
The problem of determining the adjacent vertex-distingguishing total chromatic number of a graph is NP-hard.In this article we mainly deals with the adjacent vertex-distinguishing total chromatic number for some special graphs and the graphs under some graph's operation.
In this artical we get these following conclusions:
Graph's Insert operation:There are graphs G.H and |V(G)|=|V(H)|,the insert operation of G to H is using every vetex of G dissect each edge of H and the edges of G immovabily.
Vertex expanding graph: As G is a graph we get the v(H) expending graph of G by replacing the vertex v of G a graph H,but each adjacent vertex of v just adjact to one vertex of H, that is the degree of v don't change.
Hajós sum:Let G_1 and G_2 be vertex disjoint graphs containing edges x_1y_1∈E(G_1) and x_2y_2∈E(G_2).The Hajós sum : G = (G_1,x_1y_1)+(G_2,x_2y_2) of the pairs (G_1,x_1y_1) and (G_2,x_2y_2) is obtained from G_1∪G_2 by indentifying x_1 and x_2, deleting the edge x_1y_1, x_2y_2, and adding the edge y_1y_2.
Vertex dissecting graph: As G is a graph,the vertix dissecting graph of G is obtained from G by replacing each vertex by tow independent vertices,denotedby G[I_2].
The first class graph: If G have adjactent verties of most degree andχ_(at)(G) = △(G)+2,then G is a first class graph.
The secend class graph: If G have adjactent verties of most degree andχ_(at)(G) =△(G) + 3,then G is a secend class graph.
We briefly summerize our main results as following:
Theorem 2.1.1 Insert K_n into C_n, V(K_n) = {v_1,…,v_n}, V(C_n) = {u_1,…,u_n}.We get graph S_n (n≥3).It is a graph that V(S_n) = {v_1,…,v_n;u_1,…,u_n}; E(S_n) ={v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_(i+1),u_nv_1|i= 1,…,n - 1}; Then we haveχ_(at)(S_n) =△(S_n) + 2.
Theorem 2.1.2 Insert W_n into C_(n+1),V{W_n) = {v_1,…,v_n,w},V(C_(n+1)) = {u_1,…,u_(n+1)}. We get graph G. It is a graph that V(G) = {v_1,…,v_n.w;u_1,…,u_(n-1)};E(G) = {wv_i,v_iu_i,u_iv_(i+1),wu_1,wu_(n+1)|i = 1,…,n;v_(n+1) is v_1};Then we haveλ_(at)(G) =△(G) + 1 = n + 3{n≥4).
Theorem 2.1.3 Insert H into C_n, V(H) = {v_1,…,v_n},V(C_n) = {u_1,…,u_n}.We get graph G′.It is a graph that V(G′) = {v_1,…,v_n; u_1,…,u_n}; E(G′) = {v_iu_i,v_iu(i+1), |i = 1,…,n:u_(n+1) is u_1}:∪E{H).If H satisfy the conjecture of adjacent vertex-distinguishing total coloring thatχ_(at)(H)≤△(H) + 3. Then we haveχ_(at)(G′)≤△(G′) + 3.
Theorem 2.2.1 P~n is a graph that V(P~n) = {u,v,w,v_1,…,v_n};E{P~n)={uv_i,vv_i, vw|i = 1,…,n}∪{v_iv_(i+1)|i = 1,…,n - 1}: Then we have
Theorem 2.2.2 Let G_2 be the u(K_n) expanding graph of P~n,V(P~n) = {u,v, w, v_1,…,v_n}: V(K_n) = {u_1,…,u_n}; and for u_i∈K_n, v_i∈P~n we make u_iv_i∈ G_2 (i = 1,…,n);Then we have
Theorem 2.2.3 Let H_1 be a u(S_n) expanding graph of P~n,V(S_n) = {v_1,…,v_n;u_1,…,u_n}; E(S_n) = {v_iv_j,v_iu_i|i,j = 1,…,n]∪{u_iv_(i+1),u_nv_1|i = 1,…,n - 1};V(P~n) = {u,v,w,v_1,…,v_n}: E(P~n) = [uv_i,vv_i,vw|i = 1,…,n)∪{v_iv_(i+1)i =1,…,n - 1}: and for u′_i∈S_n,v_i∈P~n we make u′_iv_i∈H_1 (i=1,…,n):Then wehaveχ_(at)(H_1) = n+3.
Theorem 2.2.4 Let H_2 be another u(S_n) expanding graph of P~n. V(P~n) ={u,v,w,v_1,…,v_n}:E(P~n) = {uv_i,vv_i,vw|i = 1,…,n}∪{v_iv_(i+1)|i = 1,…,n-1}:V(S_n) = {v_1,…,v_n,u_1,…,u_n};E(S_n) = {v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_(i+1),u_nv_1|i=1,…,n - 1}: and for v′_i∈S_n,v_i∈P~n we make v′_iv_i∈H_2 (i = 1,…,n);Then we have
Theorem 2.2.5 Let H be a u(G) expanding graph of P~n,V(G) = {u_i,…,u_n};V(P~n) = {u,v,w,v_1,v_2,…,v_n}:E(P~n) = {uv_i,vv_i,vw,(i = 1,2,…,n):v_iv_(i+1)(1 =1,…,n-1)} and for u_i∈G, v_i∈P~n we make u_iv_i∈H. (i = 1,…,n);If G satisfy theconjecture of adjacent vertex-distinguishing total coloring thatχ_(at(G)≤△(G)+3: Then we haveχ_(at)(H)≤△(H) + 3.
Theorem 2.3.1 Let G = (P~n, uv_1) + [(?)~n, u′v′_1). Then we have
Theorem 2.3.2 Let G′= (P~n,vv_n) + ((?)~n,v′v′_n), Thenχ_(at)(G′) =△(G′) + 1.
Theorem 2.3.3 Let H = (S_n, u_1v_1)+(S′_m,u′_1v′_1), Thenχ_(at)(H) = max{χ_(at)(S_n).
Theorem 2.4.1 P_n is the graph of Path, when n≠3. P_n is a first class graph, then P_n[I_2] is a first graph. too.
Theorem 2.4.2 F_n is the graph of Fan, then after dissecting, F_n satisfy thatχ_(at)(F_n[I_2]=χ_(at)(F_n[I_2]) + 1,(n≥4).
Theorem 2.4.3 W_n is the graph of Wheel, then after dissecting, W_n satisfy thatχ_(at)W_n[I_2]) =χ_(at)(W_n[I_2]) + 1. (n≥4).
Theorem 2.5.1 There are graphs S_n, C_n~1, C_n~2,C_n~3;We get a new graph H′from them with V(H′) = V(S_n)∪V{C_n~1)∪V(C_n~2)∪V(C_n~3) and E(H′) = E(S_n)∪E(C_n~1)∪E(C_n~2)∪E(C_n~3)∪(v_i~1v_i,v_i~2u_i,v_i~1v_i| = 1,…,n;v_i~j∈C_n~j;u_i,v_i∈S_n}.Then we haveχ_(at)(H′) = n+4,(n≥4).
Theorem 2.5.2 Let G_1 be the graph that satisfy u by P_2 of P~n;that not only u′v_i∈E(G_1) but also u″v_i∈E(G_1),the vertices of P_2 are u′and u″;Then we have
Theorem 2.5.3 G is an arbitrary simple graph and△(G)≥4. V(G) ={v_1,…,v_n}. we get a new graph H by the following operation:if v_iv_j∈E(G) thenwe add a new veterx u_k and adjact u_kv_i,u_kv_j;if G satisfy the conjecture of adjacent vertex-distinguishing total coloring thatχ_(at)(G)≤△(G) + 3. Then we haveχ_(at)(H)≤△(H)+3.
图G的一个正常k-染色是将k种颜色分配给G的顶点集V(G)使得两相邻顶点的颜色不同．定义色数为χ(G)=min{k|图G有k-染色}．类似的，图G的一个正常k-边染色是将k种颜色分配给G的边集E(G)．使得有公共端点的两边的颜色不同，边色数χ′(G)=min{k|图G有k-边染色}.
全染色的概念是对点染色和边染色的推广，是图染色的一个传统问题，由Vizing(1964)．Behzad(1965)各自独立提出．图的全染色是对图的点，边进行染色使得相邻或相关联的元素颜色不同．在全染色的基础上张忠辅提出了邻点可区别的全染色概念并给出了相应的猜想和两个引理．
张忠辅给出的邻点可区别的全染色定义是这样的：
设图G(V，E)为阶至少为2的简单连通图，k为正整数．函数f是从V(G)∪E(G)到C={1，2，…，k)(也记作；C=[k])的一个映射：对于任意顶点u∈V(G)，记C(u)={f(u)}∪{f(uv)|uv∈E(G))，(?)(u)=C-C(u)：
(1)对任意边uv，vw∈E(G)，且u≠w，有f(uv)≠f(vw)；
(2)对任意边uv∈E(G)，且u≠v，有f(u)≠f(v)，f(u)≠f(uv)，f(uv)≠f(v)：
(3)对于任意边uv∈E(G)，且u≠v，有C(u)≠C(v)．
若满足条件(1)，(2)．则称f为图G的一个正常k-全染色(简记为k-TC)．
若满足条件(1)，(2)，(3)，则称f为图G的一个k-邻点可区别的全染色(简记为k-AVDTC).
图G的全色数为χ_T(G)=min{k图G有k-TC}．
图G的邻点可区别的全色数为χ_(at)(G)=min{k|图G有k-AVDTC}．
下面两个关于邻点可区别的全染色的引理：
对任意阶为n(n=|V(G)|≥2)的简单连通图G，邻点可区别全色数χ_(at)(G)存在，并且χ_(at)(G)≥△(G)+1．
若图G(V，E)有两相邻的最大度顶点，则χ_(at)(G)≥△(G)+2．
张忠辅在文献中给出了关于邻点可区别全染色的猜想：
对任意阶为n(n=|V(G)|≥2)的简单连通图G．有χ_at(G)≤△(G)+3．
对于路，圈，完全图，完全二部图，星，扇，轮，树等特殊图类目前已得出了其具体的邻点可区别的全色数，并且满足上述猜想．关于上述特殊图的Mycielshi图，联图和乘积图的邻点可区别的全色数已有一些结果．另外，Petersen图，Hewood图，Tomassen图及W_n的Hajós sum图的邻点可区别的全染色也已得到一些结果．
确定一个给定图的邻点可区别的全色数是NP-困难的，本文对一些特殊图及在某些图运算下的图的邻点可区别的全染色进行了研究．
在本文我们得到如下结论：
图的插入运算：已知图G，H且有|V(G)|=|E(H)|，图G插入H是指用G的所有顶点一一对应地剖分H的所有边，原G中的边不变．
点扩充图：图G的v(H)点扩充图是指将G的某顶点v用图H代替，但v的每个邻点只分别与H的一点相邻，即：v的每个邻点的度不变．
Hajós sum：两个点不交的图G_1，G_2的Hajós sum：G=(G_1，x_1y_1)+(G_2，x_2y_2)将x_1x_2粘合为一点x，删掉边x_1y_1，x_2y_2增加边y_1y_2所得．其中x_1y_1，x_2y_2分别是G_1，G_2的边．
点分裂图：图G的点分裂图是指将G的每个顶点用两个独立的点代替得到的图，记为G[I_2]．
第一类图：若G存在相邻最大度点且χ_(at)(G)=△(G)+2，则称G为第一类图．
第二类图：若G存在相邻最大度点且χ_(at)(G)=△(G)+3，则称G为第二类图．
定理2．1．1将K_n插入G_n所得图在文献中记作S_n．此处我们仍保持原记法，其中V(C_n)={u_1，u_2，…，u_n)；V(K_n)={v_1，v_2，…，v_n)；V(S_n)={v_1，v_2，…，v_n，u_1，u2，…，u_n)；E(S_n)={v_iv_j，v_iu_i；i，j=1，…，n)∪{u_nv_1，u_1v_2，…，u_(n-1)v_n)；则：χ_(at)(S_n)=△(S_n)+2=n+3；(n≥3)．
定理2．1．2 W_n插入C_(n+1)中所得图记为G其中V(C_(n+1))={u_1，…，u_(n+1))，V(W_n)={v_1，…，v_n，w}，V(G)={u_1，…，u_(n+1)，v_1，…，v_n，w}，E(G)={wv_i，v_iv_(i+1)，wu_(n+1)，u_iv_i，v_iu_(i+1)|i=1，…，n：这里用v_(n+1)表示v_1}；则：χ_(at)(G)=△(G)+1=n+3，(n≥4)．
定理2．1．3圈C_n，V(C_n)={u_1，…，u_n)图H，V(H)={v_1，…，v_n)将H插入C_n所得图记为G′，V(G′)={u_1，…，u_n；v_1，…，v_n}，E(G′)={u_iv_i，v_iu_(i+1)，(i=1，…，n；用u_(n+1)表示u_1)∪E(H)：若H满足邻点可区别的全染色猜想，即：χ_(at)(H)≤△(H)+3，则：G′也满足χ_(at)(G′)≤△(G′)+3．
定理2．2．1图P~n(V.E)：V={u，v，w，v_1，v_2，…，v_n)：E={uv_i，vv_i，vw，(i=1，2，…n)；v_iv_(i+1)，(i=1，…，n-1))．则：
定理2．2．2令G_2表示P~n的u(K_n)扩充图，V(P~n)={u，v，w，v_1，v_2，…，v_n}；E(P~n)={uv_i，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1)}；V(K_n)={u_1，…，u_n}对于u_i∈K_nv_i∈P~n，(i=1，…，n)有：u_iv_i∈E(G_2)，(i=1，…，n)，则有：
定理2．2．3 H_1为P~n的一个u(S_n)点扩充图，V(S_n)={v′_1，v′_2，…，v′_n，u′_1，u′_2，…，u′_n}；E(S_n)={v′_iv′_j，v′_iu′_i：i，j=1，…，n}∪{u′_nv′_1，u′_1v′_2，…，u′_(n-1)v′_n}；V(P~n)={u，u，w，v_1，v_2，…，v_n)：E(P~n)={uv_i，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1)}对u′_i∈S_n，v_i∈P~n连接u′_i，v_i．(i=1，…，n)：则：χ_(at)(H_1)=n+3．
定理2．2．4令H_2为P~n的另一个u(S_n)点扩充图，对v′_i∈Sn，V(S_n)={v_1，v_2，…，v_n，u_1，u_2，…，u_n}；E(S_n)=(v_iv_j，v_iu_i；i，j=1，…，n}∪{u_nv_1，u_1v_2，…，u_(n-1)u_n}：V(P~n)={u，v，w，v_1，v_2，…，v_n}：E(P~n)={uv_i，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1))；对于v_i∈P~n连接v′_i，v_i，(i=1，…，n)，则：χ_(at)(H_2)=n+4．
定理2．2．5图G，V(G)={u_1，…，u_n}：P~n，V(P~n)={u，v，w，v_1，v_2，…，v_n)：E(P~n)={uv_1，vv_i，vw，(i=1，2，…，n)；v_iv_(i+1)，(i=1，…，n-1))且4≤χ_(at)(G)=k≤△(G)+3，设H是P~n的u(G)扩充图，(其中对于v_i∈P~n，u_i∈G(i=1，…，n)有v_iu_i∈H)，若G满足邻点可区别的全染色猜想，即：χ_(at)(G)≤△(G)+3：则：χ_(at)(H)≤△(H)+3．
定理2．3．1记(P~n，uv_1)+((P)~n，u′v′_1)=G，则
定理2．3．2记(P~n，vv_n)+((?)~n，v′v′_n)=G′：则：χ_(at)(G′)=△(G′)+1=2n+1．
定理2．3．3令H=(S_n，u_1v_1)+(S′_m，u′_1v′_1)；则：χ_(at)(H)=max{χ_(at)(S_n)，χ_at(S′_m)}．
定理2．4．1 P_n是路，则n≠3时，P_n是第一类图，则P_n[I_2]也是第一类图．
定理2．4．2 F_n是扇，则n≥4时，F_n分裂后满足χ_(at)(F_n[I_2])=△(F_n[I_2])+1．
定理2．4．3 W_n是轮，则n≥4时，W_n分裂后满足χ_(at)(W_n[I_2])=△(W_n[I_2])+1．
定理2．5．1由图S_n，C_n~1，C_n~2，C_n~3我们得到新图H′，其中V(S_n)={v_1，v_2，…，v_n，u_1，u_2，…，u_n)；V(C_n~1)={v_1~1，…，v_n~1)：V(C_n~2)={v_1~2，…，v_n~2)；V(C_n~3)={v_1~3，…，v_n~3)；V(H′)=V(S_n)∪V(C_n~1)∪V(C_n~2)V(C_n~3)；E(H′)=E(S_n)∪E(C_n~1)∪E(C_n~2)∪E(C_n~3)∪{v_i~1v_i，v_i~2u_i，v_i~3v_i~1；v_i~j∈C_n~j；u_i，v_i∈S_n；|i=1，…，n，j=1，2，3)；则：χ_(at)(H′)=n+4，(n≥4)．
定理2．5．2令G_1表示P~n的顶点u用图P_2代替所得到的图，其中P_2的顶点为{u′，u″}，u′v_i，u″v_i，(i=1，…，n)均为G_1的边，则
定理2．5．3设G为简单连通图且△(G)≥4，V(G)={v_1，…，v_n)，对G做如下操作：若v_iv_j∈E(G)则添加点u_k且连接u_kv_i，u_kv_j，如此得到的新图记做H，若G满足邻点可区别的全染色猜想即：χ_(at)(G)≤△(G)+3，则H也满足：χ_(at)(H)≤△(H)+3．
The coloring problem is one of primary fields in the study of graph theories. The coloring problem and someother graph theories are all from the study of the celebrated four color problem. With the application of the coloring problem some scholars presented and studied a few coloring problem with different restriction.
A proper k-coloring of graph G is an assignment of k colors to each vertiex in such a way that adjacent vertices have distinct colors.Difine the chromatic number of G asχ(G) = min{k|graph G has k - coloring s}. Similar,a proper k-edge-coloring of graph G is an assignment of k colors to each edge so that no two adjacent edges have the same color.The edge-chromatic number is defined asλ′(G) = min{k|graph G has k - edge - colorings}.
The totle coloring is a generalization of the coloring and the edge coloring.It's a traditional coloring problem and was introduced by Vizing(1964) and independently Behzad(1965).the total coloring is defined as all of vertices and edges of the graph are colored in such a way that no two adjacent or incident elements are colored the same.On the basis of the total coloring,Zhang Zhongfu presented the concept of the concept of the adjacent vertex-distinguishing total colorings and gave the conjecture and two results.
The definition of adjacent vertex-distinguishing total coloring by Zhang Zhongfu is as follows : Let G(V,E) is a simple and connected graph of which the order is at least 2,k is an positive integer and f is the mapping from V(G)∪E(G) to C = {1,2,…,k}orC[k].
For any vertex u∈V(G) , denote C(u) = {f(u)}∪{f(u,v)|uv∈E(G)} . (?)(u) = C- C(u) .
(1) For any edge uv , vw∈E(G) , and u≠w,there is f(uv)≠f(vw) .
(2) For any edge uv∈E(G) ,and u≠v,there is f(u)≠f(v),f(u)≠f(uv), f(uv)≠f(v) .
(3) For any edge uv∈E(G) , and u≠v, there is C(u)≠C(v) .
If (1) , (2) are satisfied , then f is called a k-total coloring of graph G(in brief, it is noted as k-TC) .
If (1), (2) , (3) are satisfied , then f is called a k-adjacent vertex-distinguishing total coloring of graph G (in brief. it is noted as k-AVDTC) .
The total chromatic number of G isχ_T (G)= min{k|G has k-TC}.
The adjacent vertex-distinguishing total chromatic number of G isλ_(at)(G) = min{k| G has k-AVDTC}.
The following results about adjacent vertex-distinguishing total coloring are right . apparently .
For a simple connected graph G of order n (n = |V(G)|≥2) , adjacent vertex-distinguishing total chromatic numberχ_(at)(G) exist , andχ_(at)(G)≥△(G) + 1.
If G(V,E) has two adjacent maximum degree vertices , thenχ_(at)(G)≥△(G) + 2.
The following conjecture is proposed by Zhang Zongfu in :
For a simple connected graph G of order n (n = |V(G)|≥2) , thenχ_(at)(G)≤△(G) + 3.
The adjacent vertex-distinguishing total chromatic number of some graphs such as path,circle,complete graph, 2-complete graph . star . fan . wheel and tree have been abtained. We also have obtained the adjacent vertex-distinguishing total chromatic number of the Mycielski graph,link graph the Cartesian product graph,Petersen graph,Heawood graph Tomassen graph,the Haj(o|¨)s sum of W_n,etc. These results are satisfied the conjecture .
The problem of determining the adjacent vertex-distingguishing total chromatic number of a graph is NP-hard.In this article we mainly deals with the adjacent vertex-distinguishing total chromatic number for some special graphs and the graphs under some graph's operation.
In this artical we get these following conclusions:
Graph's Insert operation:There are graphs G.H and |V(G)|=|V(H)|,the insert operation of G to H is using every vetex of G dissect each edge of H and the edges of G immovabily.
Vertex expanding graph: As G is a graph we get the v(H) expending graph of G by replacing the vertex v of G a graph H,but each adjacent vertex of v just adjact to one vertex of H, that is the degree of v don't change.
Hajós sum:Let G_1 and G_2 be vertex disjoint graphs containing edges x_1y_1∈E(G_1) and x_2y_2∈E(G_2).The Hajós sum : G = (G_1,x_1y_1)+(G_2,x_2y_2) of the pairs (G_1,x_1y_1) and (G_2,x_2y_2) is obtained from G_1∪G_2 by indentifying x_1 and x_2, deleting the edge x_1y_1, x_2y_2, and adding the edge y_1y_2.
Vertex dissecting graph: As G is a graph,the vertix dissecting graph of G is obtained from G by replacing each vertex by tow independent vertices,denotedby G[I_2].
The first class graph: If G have adjactent verties of most degree andχ_(at)(G) = △(G)+2,then G is a first class graph.
The secend class graph: If G have adjactent verties of most degree andχ_(at)(G) =△(G) + 3,then G is a secend class graph.
We briefly summerize our main results as following:
Theorem 2.1.1 Insert K_n into C_n, V(K_n) = {v_1,…,v_n}, V(C_n) = {u_1,…,u_n}.We get graph S_n (n≥3).It is a graph that V(S_n) = {v_1,…,v_n;u_1,…,u_n}; E(S_n) ={v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_(i+1),u_nv_1|i= 1,…,n - 1}; Then we haveχ_(at)(S_n) =△(S_n) + 2.
Theorem 2.1.2 Insert W_n into C_(n+1),V{W_n) = {v_1,…,v_n,w},V(C_(n+1)) = {u_1,…,u_(n+1)}. We get graph G. It is a graph that V(G) = {v_1,…,v_n.w;u_1,…,u_(n-1)};E(G) = {wv_i,v_iu_i,u_iv_(i+1),wu_1,wu_(n+1)|i = 1,…,n;v_(n+1) is v_1};Then we haveλ_(at)(G) =△(G) + 1 = n + 3{n≥4).
Theorem 2.1.3 Insert H into C_n, V(H) = {v_1,…,v_n},V(C_n) = {u_1,…,u_n}.We get graph G′.It is a graph that V(G′) = {v_1,…,v_n; u_1,…,u_n}; E(G′) = {v_iu_i,v_iu(i+1), |i = 1,…,n:u_(n+1) is u_1}:∪E{H).If H satisfy the conjecture of adjacent vertex-distinguishing total coloring thatχ_(at)(H)≤△(H) + 3. Then we haveχ_(at)(G′)≤△(G′) + 3.
Theorem 2.2.1 P~n is a graph that V(P~n) = {u,v,w,v_1,…,v_n};E{P~n)={uv_i,vv_i, vw|i = 1,…,n}∪{v_iv_(i+1)|i = 1,…,n - 1}: Then we have
Theorem 2.2.2 Let G_2 be the u(K_n) expanding graph of P~n,V(P~n) = {u,v, w, v_1,…,v_n}: V(K_n) = {u_1,…,u_n}; and for u_i∈K_n, v_i∈P~n we make u_iv_i∈ G_2 (i = 1,…,n);Then we have
Theorem 2.2.3 Let H_1 be a u(S_n) expanding graph of P~n,V(S_n) = {v_1,…,v_n;u_1,…,u_n}; E(S_n) = {v_iv_j,v_iu_i|i,j = 1,…,n]∪{u_iv_(i+1),u_nv_1|i = 1,…,n - 1};V(P~n) = {u,v,w,v_1,…,v_n}: E(P~n) = [uv_i,vv_i,vw|i = 1,…,n)∪{v_iv_(i+1)i =1,…,n - 1}: and for u′_i∈S_n,v_i∈P~n we make u′_iv_i∈H_1 (i=1,…,n):Then wehaveχ_(at)(H_1) = n+3.
Theorem 2.2.4 Let H_2 be another u(S_n) expanding graph of P~n. V(P~n) ={u,v,w,v_1,…,v_n}:E(P~n) = {uv_i,vv_i,vw|i = 1,…,n}∪{v_iv_(i+1)|i = 1,…,n-1}:V(S_n) = {v_1,…,v_n,u_1,…,u_n};E(S_n) = {v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_(i+1),u_nv_1|i=1,…,n - 1}: and for v′_i∈S_n,v_i∈P~n we make v′_iv_i∈H_2 (i = 1,…,n);Then we have
Theorem 2.2.5 Let H be a u(G) expanding graph of P~n,V(G) = {u_i,…,u_n};V(P~n) = {u,v,w,v_1,v_2,…,v_n}:E(P~n) = {uv_i,vv_i,vw,(i = 1,2,…,n):v_iv_(i+1)(1 =1,…,n-1)} and for u_i∈G, v_i∈P~n we make u_iv_i∈H. (i = 1,…,n);If G satisfy theconjecture of adjacent vertex-distinguishing total coloring thatχ_(at(G)≤△(G)+3: Then we haveχ_(at)(H)≤△(H) + 3.
Theorem 2.3.1 Let G = (P~n, uv_1) + [(?)~n, u′v′_1). Then we have
Theorem 2.3.2 Let G′= (P~n,vv_n) + ((?)~n,v′v′_n), Thenχ_(at)(G′) =△(G′) + 1.
Theorem 2.3.3 Let H = (S_n, u_1v_1)+(S′_m,u′_1v′_1), Thenχ_(at)(H) = max{χ_(at)(S_n).
Theorem 2.4.1 P_n is the graph of Path, when n≠3. P_n is a first class graph, then P_n[I_2] is a first graph. too.
Theorem 2.4.2 F_n is the graph of Fan, then after dissecting, F_n satisfy thatχ_(at)(F_n[I_2]=χ_(at)(F_n[I_2]) + 1,(n≥4).
Theorem 2.4.3 W_n is the graph of Wheel, then after dissecting, W_n satisfy thatχ_(at)W_n[I_2]) =χ_(at)(W_n[I_2]) + 1. (n≥4).
Theorem 2.5.1 There are graphs S_n, C_n~1, C_n~2,C_n~3;We get a new graph H′from them with V(H′) = V(S_n)∪V{C_n~1)∪V(C_n~2)∪V(C_n~3) and E(H′) = E(S_n)∪E(C_n~1)∪E(C_n~2)∪E(C_n~3)∪(v_i~1v_i,v_i~2u_i,v_i~1v_i| = 1,…,n;v_i~j∈C_n~j;u_i,v_i∈S_n}.Then we haveχ_(at)(H′) = n+4,(n≥4).
Theorem 2.5.2 Let G_1 be the graph that satisfy u by P_2 of P~n;that not only u′v_i∈E(G_1) but also u″v_i∈E(G_1),the vertices of P_2 are u′and u″;Then we have
Theorem 2.5.3 G is an arbitrary simple graph and△(G)≥4. V(G) ={v_1,…,v_n}. we get a new graph H by the following operation:if v_iv_j∈E(G) thenwe add a new veterx u_k and adjact u_kv_i,u_kv_j;if G satisfy the conjecture of adjacent vertex-distinguishing total coloring thatχ_(at)(G)≤△(G) + 3. Then we haveχ_(at)(H)≤△(H)+3.
引文
[1].Bela Bollobas,Modern Graph Theory,Springer-Verlag New York,Inc.1998.
[2].Zhongfu zhang etc, On The Adjacent Vertex-Distinguish Total Coloring of Graphs,Science in China.SerA.10(2004):574-583.
[3].Vizing.V.G..On an estimate of the chromatic class of a p-graph(Russian),Diskret. Analiz.3(1964)25-30.
[4].Behzad.M..Graphs and Their chromatic Numbers,PhD.thesis. Michigan State University(1965).
[5].Behzad.M.The total chromatic numberofa graph:a survey, in Combinatoriac Mathematics and its Applications,Academic Press(1971)1-8.
[6].Behzad.Graphs and their chromatic numbers.Doctoral Thesis.Michigan State University. 1965.
[7].M.Behzad and H.Radjavi.Structure of regular total graphs,J.London Math.Soc. 44(1969).433-436.
[8].Zhang zhongfu.A survey of graph coloring,Collegeof Mathematics and Information Science.
[9].J.A.Bondy,U.S.R.Murty.Graph Theory with Applications.North-Holland.1976.
[10].A.Brandst(?)dt,Van Bang Le,Jeremy P.Spinrad,Graph Classes.Philadelphia:Society for Industrial and Applied Mathematics,C1999.
[11].Jensen T.R.Toft B.:Graph Coloring Problems.Wiley,New York (1995).
[12].Anthony M.Biggs N.:The mean chormatic number of paths and cycles,Didcrete Math 120(1993),227-231.
[13].Asratian A..KramalianR.:Investigation on interbal edge-coloring of graphs. J.Combin.Theory,Ser.B 62(1994)34-43.
[14].D.Konig.Uber graphen und iher anwendung auf determinantentheorie und meng-enlehre.Math.Ann..77,pp.(1916)453-465.
[15].Alon N.Restricted Colorings of Graphs.In:K.Walker.editor. Surveys inCombinatorics :Proc.14th British Combinatorial Conference.Pages1-33.Cambridge University Press 1933 .
[16].Lovász,L.,Kneser's conjecture.Chromatic number,and homotopy,J.Comb.Theory (Ser.A)25(1978)319-324.
[17].Erd(?)s P,Wilson R.:On the chromatic index of almost all graphs,J.Combin. Theory.Ser.B 23(1977)255-257.
[18].S.Klavazar.A note on the fractional chromatic number and the lexicographic-product of graphs,preprint. 1996.
[19].D.C.Fisher,Fractional colorings with large denominators,J.Graph Theory,20(1995). 403-409.
[20].M.Larsen,J.Propp and D.Ullman.The fractional chromatic number of Mycielski's graphs. J.Graph Theory,19(1995),411-416.
[21].Mycielski,J..Sur Le coloring des graphes,Colloq.Math.3(1955)161-162.
[22].Brooks.R.L.On coloring the nodes of a network.Proc.Cambridge Phil.Soc 37(1941) 194-197.
[23]．杨义先等，乘积图的全色数．应用数学， 1999．12(2)：108-111．
[24].Dietel Reinhard.Graph Theory.Springer Verlag New York.Inc.1997.
[25].Yap H.P.,Total coloring of graphs.Lecture Notes in Mathematics 1623(1996)1-131.
[26].Hansen P.,Marcotte O..Graph coloring and application,AMS providence.Rhode Island USA. 1999.
[27]．孙艳丽．图的全染色， (邻)点可区别的全染色及分数染色，山东师范大学硕 士学位论文，(2006)22-27．
[28].Behzad.M..Graphs and Their Chromatic Numbers,Ph.D.thesis,Michigan State University(1965).
[29].Behzad.M..The total chromatic number of a graph:a survey,in Com-binatorial Mathematics and its Applications,Academic Press(1971)1-8.
[30].Sandi Klav(?)ar.Coloring graph products-A survey,Diserete Mathematics. 155(1996) 135-145.
[31].N.(?)i(?)ek and S.Klav(?)ar.On the chromatic number of the lexicographic product and the Cartesian sum of graphs,Discrete Math.134(1994)17-24.
[32].Erd(?)s P.:Some remarks on the theory of graphs.Bull.Amer.Sco.53(1947),292-294.
[33].X.Zhu,Circular chromatic number,a survey,Discrete Math. 1997.
[34] H.P.Yap and K.H. Chew, Total chromatic number of graphs of high degree.II, J.Australian Math.Soc.,Ser.A,53,pp. 1992,219-228.
[35]. A.J.W.Hiltion and H.R.Hind,Total chromatic number of graphs having large maximum degree, Discrete Math.,117,pp. 1993,127～140.
[36]. O.V.Borodin.A.V.Kostochka and D.R.Woodall,List edge and list total colorings of multigraphs,J. Combinatorial Theory Series B.71,pp.1997,184～204.
[37]. A.V.Kostochka.The total chromatic number of any multigraph with maximum degree five is at most seven,Discrete Math.,162,pp.1996,199—214.
[38]. P.N.Balister,B.Bollobas.R.H.Shelp,Vertex distinguishing colorings of graphs with △(G) = 2,Discrete Math.252(2002) 17-29.
[39]. C.Bazgan,A.Harkat-Benhamdine,Hao Li,M.Woiniak,On the vertex-distinguishing proper edge-coloring of graphs,J.Combin.Theory Ser.B 75(1999)288～301.
[40]. A.C.Burris and R.H.Schelp Vertex-distinguishing proper edge-colorings.J of Graph Theory. 1997.26:73-82.
[41]. G.Chartrand,L.Lesniak-Foster,Graph and Digraphs,Ind.Edition,Wadsworth Brooks/Cole,Monterey,CA,1986.
[42]. Zhongfu Zhang.Linzhong Liu,Jianfang Wang.Adjacent strong edge coloring of graphs. Applied Math.Letters,2002,15:623-626.
[2].Zhongfu zhang etc, On The Adjacent Vertex-Distinguish Total Coloring of Graphs,Science in China.SerA.10(2004):574-583.
[3].Vizing.V.G..On an estimate of the chromatic class of a p-graph(Russian),Diskret. Analiz.3(1964)25-30.
[4].Behzad.M..Graphs and Their chromatic Numbers,PhD.thesis. Michigan State University(1965).
[5].Behzad.M.The total chromatic numberofa graph:a survey, in Combinatoriac Mathematics and its Applications,Academic Press(1971)1-8.
[6].Behzad.Graphs and their chromatic numbers.Doctoral Thesis.Michigan State University. 1965.
[7].M.Behzad and H.Radjavi.Structure of regular total graphs,J.London Math.Soc. 44(1969).433-436.
[8].Zhang zhongfu.A survey of graph coloring,Collegeof Mathematics and Information Science.
[9].J.A.Bondy,U.S.R.Murty.Graph Theory with Applications.North-Holland.1976.
[10].A.Brandst(?)dt,Van Bang Le,Jeremy P.Spinrad,Graph Classes.Philadelphia:Society for Industrial and Applied Mathematics,C1999.
[11].Jensen T.R.Toft B.:Graph Coloring Problems.Wiley,New York (1995).
[12].Anthony M.Biggs N.:The mean chormatic number of paths and cycles,Didcrete Math 120(1993),227-231.
[13].Asratian A..KramalianR.:Investigation on interbal edge-coloring of graphs. J.Combin.Theory,Ser.B 62(1994)34-43.
[14].D.Konig.Uber graphen und iher anwendung auf determinantentheorie und meng-enlehre.Math.Ann..77,pp.(1916)453-465.
[15].Alon N.Restricted Colorings of Graphs.In:K.Walker.editor. Surveys inCombinatorics :Proc.14th British Combinatorial Conference.Pages1-33.Cambridge University Press 1933 .
[16].Lovász,L.,Kneser's conjecture.Chromatic number,and homotopy,J.Comb.Theory (Ser.A)25(1978)319-324.
[17].Erd(?)s P,Wilson R.:On the chromatic index of almost all graphs,J.Combin. Theory.Ser.B 23(1977)255-257.
[18].S.Klavazar.A note on the fractional chromatic number and the lexicographic-product of graphs,preprint. 1996.
[19].D.C.Fisher,Fractional colorings with large denominators,J.Graph Theory,20(1995). 403-409.
[20].M.Larsen,J.Propp and D.Ullman.The fractional chromatic number of Mycielski's graphs. J.Graph Theory,19(1995),411-416.
[21].Mycielski,J..Sur Le coloring des graphes,Colloq.Math.3(1955)161-162.
[22].Brooks.R.L.On coloring the nodes of a network.Proc.Cambridge Phil.Soc 37(1941) 194-197.
[23]．杨义先等，乘积图的全色数．应用数学， 1999．12(2)：108-111．
[24].Dietel Reinhard.Graph Theory.Springer Verlag New York.Inc.1997.
[25].Yap H.P.,Total coloring of graphs.Lecture Notes in Mathematics 1623(1996)1-131.
[26].Hansen P.,Marcotte O..Graph coloring and application,AMS providence.Rhode Island USA. 1999.
[27]．孙艳丽．图的全染色， (邻)点可区别的全染色及分数染色，山东师范大学硕 士学位论文，(2006)22-27．
[28].Behzad.M..Graphs and Their Chromatic Numbers,Ph.D.thesis,Michigan State University(1965).
[29].Behzad.M..The total chromatic number of a graph:a survey,in Com-binatorial Mathematics and its Applications,Academic Press(1971)1-8.
[30].Sandi Klav(?)ar.Coloring graph products-A survey,Diserete Mathematics. 155(1996) 135-145.
[31].N.(?)i(?)ek and S.Klav(?)ar.On the chromatic number of the lexicographic product and the Cartesian sum of graphs,Discrete Math.134(1994)17-24.
[32].Erd(?)s P.:Some remarks on the theory of graphs.Bull.Amer.Sco.53(1947),292-294.
[33].X.Zhu,Circular chromatic number,a survey,Discrete Math. 1997.
[34] H.P.Yap and K.H. Chew, Total chromatic number of graphs of high degree.II, J.Australian Math.Soc.,Ser.A,53,pp. 1992,219-228.
[35]. A.J.W.Hiltion and H.R.Hind,Total chromatic number of graphs having large maximum degree, Discrete Math.,117,pp. 1993,127～140.
[36]. O.V.Borodin.A.V.Kostochka and D.R.Woodall,List edge and list total colorings of multigraphs,J. Combinatorial Theory Series B.71,pp.1997,184～204.
[37]. A.V.Kostochka.The total chromatic number of any multigraph with maximum degree five is at most seven,Discrete Math.,162,pp.1996,199—214.
[38]. P.N.Balister,B.Bollobas.R.H.Shelp,Vertex distinguishing colorings of graphs with △(G) = 2,Discrete Math.252(2002) 17-29.
[39]. C.Bazgan,A.Harkat-Benhamdine,Hao Li,M.Woiniak,On the vertex-distinguishing proper edge-coloring of graphs,J.Combin.Theory Ser.B 75(1999)288～301.
[40]. A.C.Burris and R.H.Schelp Vertex-distinguishing proper edge-colorings.J of Graph Theory. 1997.26:73-82.
[41]. G.Chartrand,L.Lesniak-Foster,Graph and Digraphs,Ind.Edition,Wadsworth Brooks/Cole,Monterey,CA,1986.
[42]. Zhongfu Zhang.Linzhong Liu,Jianfang Wang.Adjacent strong edge coloring of graphs. Applied Math.Letters,2002,15:623-626.