【作者】 刘萍；

【导师】 孙磊；

【作者基本信息】 山东师范大学 ， 应用数学， 2008， 硕士

【摘要】 染色问题是图论研究的经典领域，是图论研究中一个很活跃的话题．染色问题及许多图理论均源自四色问题的研究，随着染色问题在现实中被广泛应用，各类染色问题被相继提出并加以发展，研究．图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₁，G₂的Hajós sum：G=（G₁，x₁y₁）+（G₂，x₂y₂）将x₁x₂粘合为一点x，删掉边x₁y₁，x₂y₂增加边y₁y₂所得．其中x₁y₁，x₂y₂分别是G₁，G₂的边．点分裂图：图G的点分裂图是指将G的每个顶点用两个独立的点代替得到的图，记为G[I₂]．第一类图：若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₁，u₂，…，u_n)；V（K_n）={v₁，v₂，…，v_n)；V（S_n）={v₁，v₂，…，v_n，u₁，u2，…，u_n)；E（S_n）={v_iv_j，v_iu_i；i，j=1，…，n)∪{u_nv₁，u₁v₂，…，u_n-1v_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₁，…，u_n+1)，V（W_n）={v₁，…，v_n，w}，V（G）={u₁，…，u_n+1，v₁，…，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₁}；则：χ_at（G）=△（G）+1=n+3，（n≥4）．定理2．1．3圈C_n，V（C_n）={u₁，…，u_n)图H，V（H）={v₁，…，v_n)将H插入C_n所得图记为G′，V（G′）={u₁，…，u_n；v₁，…，v_n}，E（G′）={u_iv_i，v_iu_i+1，(i=1，…，n；用u_n+1表示u₁)∪E（H）：若H满足邻点可区别的全染色猜想，即：χ_at（H）≤△（H）+3，则：G′也满足χ_at（G′）≤△（G′）+3．定理2．2．1图Pⁿ（V.E）：V={u，v，w，v₁，v₂，…，v_n)：E={uv_i，vv_i，vw，（i=1，2，…n）；v_iv_i+1，（i=1，…，n-1）)．则：定理2．2．2令G₂表示Pⁿ的u（K_n）扩充图，V（Pⁿ）={u，v，w，v₁，v₂，…，v_n}；E（Pⁿ）={uv_i，vv_i，vw，（i=1，2，…，n）；v_iv_i+1，（i=1，…，n-1）}；V（K_n）={u₁，…，u_n}对于u_i∈K_nv_i∈Pⁿ，（i=1，…，n）有：u_iv_i∈E（G₂），（i=1，…，n），则有：定理2．2．3 H₁为Pⁿ的一个u（S_n）点扩充图，V（S_n）={v′₁，v′₂，…，v′_n，u′₁，u′₂，…，u′_n}；E（S_n）={v′_iv′_j，v′_iu′_i：i，j=1，…，n}∪{u′_nv′₁，u′₁v′₂，…，u′_n-1v′_n}；V（Pⁿ）={u，u，w，v₁，v₂，…，v_n)：E（Pⁿ）={uv_i，vv_i，vw，（i=1，2，…，n）；v_iv_i+1，（i=1，…，n-1）}对u′_i∈S_n，v_i∈Pⁿ连接u′_i，v_i．（i=1，…，n）：则：χ_at（H₁）=n+3．定理2．2．4令H₂为Pⁿ的另一个u（S_n）点扩充图，对v′_i∈Sn，V（S_n）={v₁，v₂，…，v_n，u₁，u₂，…，u_n}；E（S_n）=(v_iv_j，v_iu_i；i，j=1，…，n}∪{u_nv₁，u₁v₂，…，u_n-1u_n}：V（Pⁿ）={u，v，w，v₁，v₂，…，v_n}：E（Pⁿ）={uv_i，vv_i，vw，（i=1，2，…，n）；v_iv_i+1，（i=1，…，n-1）)；对于v_i∈Pⁿ连接v′_i，v_i，（i=1，…，n），则：χ_at（H₂）=n+4．定理2．2．5图G，V（G）={u₁，…，u_n}：Pⁿ，V（Pⁿ）={u，v，w，v₁，v₂，…，v_n)：E（Pⁿ）={uv₁，vv_i，vw，（i=1，2，…，n）；v_iv_i+1，（i=1，…，n-1）)且4≤χ_at（G）=k≤△（G）+3，设H是Pⁿ的u（G）扩充图，（其中对于v_i∈Pⁿ，u_i∈G（i=1，…，n）有v_iu_i∈H），若G满足邻点可区别的全染色猜想，即：χ_at（G）≤△（G）+3：则：χ_at（H）≤△（H）+3．定理2．3．1记（Pⁿ，uv₁）+（（P）ⁿ，u′v′₁）=G，则定理2．3．2记（Pⁿ，vv_n）+（（?）ⁿ，v′v′_n）=G′：则：χ_at（G′）=△（G′）+1=2n+1．定理2．3．3令H=（S_n，u₁v₁）+（S′_m，u′₁v′₁）；则：χ_at（H）=max{χ_at（S_n），χ_at（S′_m）}．定理2．4．1 P_n是路，则n≠3时，P_n是第一类图，则P_n[I₂]也是第一类图．定理2．4．2 F_n是扇，则n≥4时，F_n分裂后满足χ_at（F_n[I₂]）=△（F_n[I₂]）+1．定理2．4．3 W_n是轮，则n≥4时，W_n分裂后满足χ_at（W_n[I₂]）=△（W_n[I₂]）+1．定理2．5．1由图S_n，C_n¹，C_n²，C_n³我们得到新图H′，其中V（S_n）={v₁，v₂，…，v_n，u₁，u₂，…，u_n)；V（C_n¹）={v₁¹，…，v_n¹)：V（C_n²）={v₁²，…，v_n²)；V（C_n³）={v₁³，…，v_n³)；V（H′）=V（S_n）∪V（C_n¹）∪V（C_n²）V（C_n³）；E（H′）=E（S_n）∪E（C_n¹）∪E（C_n²）∪E（C_n³）∪{v_i¹v_i，v_i²u_i，v_i³v_i¹；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₁表示Pⁿ的顶点u用图P₂代替所得到的图，其中P₂的顶点为{u′，u″}，u′v_i，u″v_i，（i=1，…，n）均为G₁的边，则定理2．5．3设G为简单连通图且△（G）≥4，V（G）={v₁，…，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．更多还原

【Abstract】 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₁ and G₂ be vertex disjoint graphs containing edges x₁y₁∈E（G₁） and x₂y₂∈E（G₂）.The Hajós sum : G = （G₁,x₁y₁）+（G₂,x₂y₂） of the pairs （G₁,x₁y₁） and （G₂,x₂y₂） is obtained from G₁∪G₂ by indentifying x₁ and x₂, deleting the edge x₁y₁, x₂y₂, and adding the edge y₁y₂.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₂].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₁,…,v_n}, V（C_n） = {u₁,…,u_n}.We get graph S_n （n≥3）.It is a graph that V（S_n） = {v₁,…,v_n;u₁,…,u_n}; E（S_n） ={v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_i+1,u_nv₁|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₁,…,v_n,w},V(C_n+1) = {u₁,…,u_n+1}. We get graph G. It is a graph that V（G） = {v₁,…,v_n.w;u₁,…,u_n-1};E（G） = {wv_i,v_iu_i,u_iv_i+1,wu₁,wu_n+1|i = 1,…,n;v_n+1 is v₁};Then we haveλ_at（G） =△（G） + 1 = n + 3{n≥4).Theorem 2.1.3 Insert H into C_n, V（H） = {v₁,…,v_n},V（C_n） = {u₁,…,u_n}.We get graph G′.It is a graph that V（G′） = {v₁,…,v_n; u₁,…,u_n}; E（G′） = {v_iu_i,v_iu（i+1）, |i = 1,…,n:u_n+1 is u₁}:∪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ⁿ is a graph that V（Pⁿ） = {u,v,w,v₁,…,v_n};E{Pⁿ)={uv_i,vv_i, vw|i = 1,…,n}∪{v_iv_i+1|i = 1,…,n - 1}: Then we haveTheorem 2.2.2 Let G₂ be the u（K_n） expanding graph of Pⁿ,V（Pⁿ） = {u,v, w, v₁,…,v_n}: V（K_n） = {u₁,…,u_n}; and for u_i∈K_n, v_i∈Pⁿ we make u_iv_i∈ G₂ （i = 1,…,n）;Then we haveTheorem 2.2.3 Let H₁ be a u（S_n） expanding graph of Pⁿ,V（S_n） = {v₁,…,v_n;u₁,…,u_n}; E（S_n） = {v_iv_j,v_iu_i|i,j = 1,…,n]∪{u_iv_i+1,u_nv₁|i = 1,…,n - 1};V（Pⁿ） = {u,v,w,v₁,…,v_n}: E（Pⁿ） = [uv_i,vv_i,vw|i = 1,…,n)∪{v_iv_i+1i =1,…,n - 1}: and for u′_i∈S_n,v_i∈Pⁿ we make u′_iv_i∈H₁ （i=1,…,n）:Then wehaveχ_at（H₁） = n+3.Theorem 2.2.4 Let H₂ be another u（S_n） expanding graph of Pⁿ. V（Pⁿ） ={u,v,w,v₁,…,v_n}:E（Pⁿ） = {uv_i,vv_i,vw|i = 1,…,n}∪{v_iv_i+1|i = 1,…,n-1}:V（S_n） = {v₁,…,v_n,u₁,…,u_n};E（S_n） = {v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_i+1,u_nv₁|i=1,…,n - 1}: and for v′_i∈S_n,v_i∈Pⁿ we make v′_iv_i∈H₂ （i = 1,…,n）;Then we haveTheorem 2.2.5 Let H be a u（G） expanding graph of Pⁿ,V（G） = {u_i,…,u_n};V（Pⁿ） = {u,v,w,v₁,v₂,…,v_n}:E（Pⁿ） = {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ⁿ 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ⁿ, uv1） + [（?）ⁿ, u′v′1}. Then we haveTheorem 2.3.2 Let G′= （Pⁿ,vv_n） + （（?）ⁿ,v′v′_n）, Thenχ_at（G′） =△（G′） + 1.Theorem 2.3.3 Let H = （S_n, u₁v₁）+（S′_m,u′₁v′₁）, 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₂] 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₂]=χ_at（F_n[I₂]） + 1,（n≥4）.Theorem 2.4.3 W_n is the graph of Wheel, then after dissecting, W_n satisfy thatχ_atW_n[I₂]) =χ_at（W_n[I₂]） + 1. （n≥4）.Theorem 2.5.1 There are graphs S_n, C_n¹, C_n²,C_n³;We get a new graph H′from them with V（H′） = V（S_n）∪V{C_n¹)∪V（C_n²）∪V（C_n³） and E（H′） = E（S_n）∪E（C_n¹）∪E（C_n²）∪E（C_n³）∪(v_i¹v_i,v_i²u_i,v_i¹v_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₁ be the graph that satisfy u by P₂ of Pⁿ;that not only u′v_i∈E（G₁） but also u″v_i∈E（G₁）,the vertices of P₂ are u′and u″;Then we haveTheorem 2.5.3 G is an arbitrary simple graph and△（G）≥4. V（G） ={v₁,…,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.更多还原