【作者】 韩淑芹；

【导师】 孙磊；

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

【摘要】 染色问题是图论研究的经典领域，它源自于四色定理的研究，是图论研究中一个很活跃的课题。随着染色问题在现实中被广泛应用，各类染色问题被相继提出并加以发展、应用。图G的一个（正常）k-染色是将k种染色分配给G的顶点集V（G），使得相邻两顶点的颜色不同。定义色数为：x（G）=min{k|图G有k-染色}。类似的，图G的一个（正常）k-边染色是将k种染色分配给G的边集E（G），使得有公共端点的两边的颜色不同。边色数x′（G）=min{k|图G有k-边染色}。全染色的概念是对点染色和边染色的推广，是图论染色的一个传统问题，由Vizing（1964）和Behzad（1965）各自独立提出的。图的全染色是对图的点，边进行染色，使得相邻或相关联的两元素染色不同。图的全色数xT（G）=min{k|图G有一个k-全染色}。在全染色的基础上，张忠辅提出了邻点可区别的全染色的概念并给出了相应的猜想和两个引理。张忠辅定义的邻点可区别的全染色如下：设G（V，E）为阶不小于2的简单连通图，k为正整数，令映射f：V（G）∪E（G）→{1，2，…，k}。对任意u∈V（G），如果（1）对任意uv，vw∈E（G），u≠w，有f（uv）≠f（vw）。（2）对任意uv∈E（G），有f（u）≠f（v），f（u）≠f（uv），f（uv）≠f（v）。则称f为图G的一个k-全染色，简记为k-TC。若还满足（3）对任意uv∈E（G），C（u）≠C（v），其中C（u）={f（u）}∪{f（uv）|uv∈E（G）}。那么称f为图G的一个k-邻点可区别全染色，简记为k-AVDTC。图G的全色数xT（G）（或记为x″（G））=min{k|图G有k-全染色}。图G的邻点可区别的全色数xat（G）=min{k|图G有k-AVDTC}。张忠辅给出了关于邻点可区别全染色的两个引理：对任意阶为n（n≥2）的简单连通图G，邻点可区别全色数xat（G）存在，并且xat（G）≥△（G）+1。若图G（V，E）有两个相邻的最大度点，则有xat（G）≥△（G）+2。张忠辅在文献中给出了邻点可区别全色数猜想：对任意阶为n（n≥2）的简单连通图G，有xat（G）≤△（G）+3。确定一任意给定图的邻点可区别全色数是NP-困难的。目前关于路，圈，完全图，完全二部图，星，扇，轮，树等特殊图的邻点可区别全色数已给出。另外上述特殊图的Mycielski图，联图和乘积图的邻点可区别全色数已有一些结果。同时，Petersen图，Heawood图，Thomassen图的邻点可区分全色数也已得到结果。1880年，边染色的概念被提出，在边染色问题的研究中有著名的四色定理。1964年，Vizing得出一个重要的定理即对任意的简单图G，有△（G）≤x′（G）≤△（G）+1。1974年，R．P．Gupta对边覆盖染色进行了研究。图G的边覆盖染色是对图G的所有边进行染色使得每种颜色在每个顶点上至少出现一次。满足图G有一个k-边覆盖染色的最大正整数k称为图G的边覆盖色数，记为x′_c（G）。同年，Gupta证明了对任意的简单图G，有δ（G）-1≤x′_c（G）≤δ（G）。若x′_c（G）=δ（G），则称G是第一类的。若x′_c（G）=δ（G）-1，则称G是第二类的。刘桂珍老师及苗连英，宋惠敏等对图的边覆盖染色进行了进一步的研究并取得了丰硕的成果。2006年，孙磊老师受边覆盖染色的启发提出了全色极大团染色的概念。全色极大团染色是对图G的顶点进行染色，使得G的每个极大团所有颜色均出现。满足图G有一个k-全色极大团染色的最大正整数k称为图G的全色极大团色数，记为xmaxcT（G）。显然有xmaxcT（G）≤min{|H||H为G的极大团}。本文一部分主要探讨了轮，完全图的Hajós sum的邻点可区别全色数。另外还得到了特殊图P_n^k，花G的邻点可区别全色数。另一部分讨论了特定条件下全色极大团染色与边覆盖染色的等价性，给出了联图，复合图，笛卡尔乘积图，外平面图的全色极大团色数，并给出了K_n-M，C_n，Mycielski图，类Mycielski图的全色极大团色数。在本文中，我们主要得到结论如下：两个点不交的图G₁和G₂的Hajós sum G=（G₁，x₁y₁）+（G₂，x₂y₂）是由G₁∪G₂粘合x₁，x₂为一个点，删去边x₁y₁，x₂y₂增加边y₁y₂所得。其中x₁y₁∈E（G₁），x₂y₂∈E（G₂）。令W_n=K₁∨C_n，V（W_n）={v₁，v₂，…，v_n，v₀)，E（W_n）={v_iv_i+1|i=1，2，…，n；v_n+1=v₁}∪{v₀v_i|i=1，2，…，n}，W′_n为W_n的复制。定理2．1．1 Hajós sum W_n^*=（W_n，v₁v₂）+（W′_n，v′₁v′₂），粘合v₁，v′₁为一个点v₁，则定理2．1．2 Hajós sum G=（W_n，v₀v₁）+（W′_n，v′₀v′₁），粘合v₀，v′₀为一个点v₀，则xat（G）=2n-1。定理2．1．3 Hajós sum G=（K_m，v₁v₂）+（K_n，v′₁v′₂），粘合v₁，v′₁为一个点v₁，则在含有n个顶点的路P_n上，当且仅当两点距离为k时添加一条边，所得的图称为P_n^k图。定理2．2．1对图P_n^k，k=[n/2]，有Xat（P_n^k）=5。K_n是具有n个顶点v₁，…v_n的完全图，在K_n的每个顶点v_i上悬挂m_i（1≤i≤n）个点v_i1，…，v_imi，这m_i个点形成一条路v_i1v_i2…v_imi，如此得到花G。定理2．2．2对花G，不妨设m_s=max_k=1，2…n m_k，有对任意的图G，其线图L（G）的顶点集为E（G），两点之间有边当且仅当在图G中两边相邻。对任意的图G，其全图T（G）的顶点集为V（G）∪E（G），两元素间有边当且仅当在图G中两元素相邻或相关联。记p=min{|G′||G″为G的极大团}。q=min{|H′||H′为H的极大团}。定理3．1．1若存在H使G=L（H）且p≥4。则图G的全色极大团染色等价于图H的边覆盖染色。Gupta定理的内容是对任意的简单图G。有δ（G）-1≤x′_c（G）≤δ（G）。推论3．1．2 Gupta定理等价于下面两种情形：（1）若存在H使G=L（H）且p≥4，则有p-1≤xmaxcT（G）≤p。（2）若存在H使G=T（H）且p≥4，则有p-1≤xmaxcT（G）≤p。M是完全图K_n的某一匹配，则K_n-M的所有极大团点数相同，均为n-2|M|+|M|=n-|M|，且K_n-M的每个极大团的点集形式为V（K_n）＼V（M）与|M|个点的并集，这|M|个点是从M的每个匹配边连结的两点中任意一点组成的。定理3．1．3完全图K_n，N（?）E（K_n）且δ（K_n-N）≥n-2，则xmaxcT（K_n-N）=n-|N|。定理3．1．4 G=C_n，则两个图G和H的联图G∨H定义为：V（G∨H）=V（G）∪V（H），E（G∨H）=E（G）∪E（H）∪{uv|u∈V（G）。v∈V（H）}。定理3．1．5对任意简单连通图G，H，有xmaxcT（G∨H）=xmaxcT（G）+xmaxcT（H）。两个图G和H的复合图G[H]定义为：它的顶点集为V（G）×V（H），其中两个顶点（u，v），（u′，v′）相邻当且仅当或者uu′∈E（G），或者u=u′，vv′∈E（H）。定理3．1．6图G，H分别满足xmaxcT（G）=p，xmaxcT（H）=q，则有xmaxcT（G[H]）=xmaxcT（G）xmaxcT（H）。并不是对所有的简单连通图G，H均有xmaxcT（G[H]）=xmaxcT（G）xmaxcT（H）。例如：G=P_n，H=C_2m+1，而xmaxcT(P_n[C_2m+1]=3≠2×1。对于图G和H，设V（G）={u₁，u₂，…，u_m}，V（H）：{v₁，v₂，…，v_n}。它们的笛卡尔乘积G×H定义为：V（G×H）={w_ij=（u_i，v_j），1≤i≤m，1≤j≤n}，E（G×H）={w_ijw_kl，i=k和v_jv_l∈E（H）或j=l和u_iu_k∈E（G）}。定理3．1．7若p-1≤xmaxcT（G）≤p，q-1≤xmaxcT（H）≤q，则有xmaxcT（G×H）=min{xmaxcT（G），xmaxcT（H）}。我们称由Mycielski作图法得到的图为Mycielski图。给定图G，其顶点集V={v₁，v₂，…，v_n}。图G的Mycielski图（记为M（G））定义为：顶点集V（M（G））=V∪{v′₁，v′₂，…，v′_n，w}，边集E（M（G））=E（G）∪{v_iv′_j|v_iv_j∈E（G），i，j=1，…，n}∪{v′_iw|i=1，…，n}。定理3．2．1对任意简单连通图G，均有xmaxcT（M（G））=1。定理3．2．2对任意简单连通图G，令u（G）=M（G）-w，则xmaxcT（u（G））=xmaxcT（G）。给定图G，顶点集为V={v₁，v₂，…，v_n}。图G的类M构造图（记为S（G））定义如下：V（S（G））=V（G）∪V（G′）∪{w}，G′为G的复制。边集E（S（G））=E（G）∪E（G′）∪{v_iv′_i|v_i∈V（G），i=1，2，…，n}∪{v_iv′_j|v_iv_j∈E（G），i，j=1，2，…n}∪{v′_iw|i=1，2，…，n}。对图S_m（G）定义为：S₁（G）=S（G）。V（S_m（G））=V（G）∪V（G′）∪V（G″）∪…∪V(G^（m）∪{w}，E（S_m（G））=E（G）∪E（G′）∪E（G″）∪…∪E(G^（m）)∪{v_i^（j）v_i^（j+1）|v_i∈V（G），i=1，2，…，n；j=0，1，…，m-1；v_i^（0）=v_i}∪{v_i^（k）v_j^（k+1）|v_iv_j∈E（G），i，j=1，2，…，n；k=0，1，…，m-1}∪{v_i^（m）w|v_i∈V（G），i=1，2，…，n}。定理3．2．3对任意简单连通图G，有xmaxcT（S（G））=xmaxcT（G）+1。推论3．2．4令S₀（G）=G∨{w}，则有xmaxcT（S₀（G））=xmaxcT（G）+1。定理3．2．5对任意简单连通图G，有xmaxcT（S_m（G））=xmaxcT（G）+1。定理3．2．6若G为外平面图且p=2，则定理3．2．7若G为外平面图且p=3，则xmaxcT（G）=3。更多还原

【Abstract】 The coloring problem is one of primary fields in the study of graph theories.Itis from the study of the celebrated four color problem.With the application ofthe coloring problem some scholars presented and studied a few coloring problemwith different restriction.A （proper）k-coloring of graph G is an assignment of one of k colors to each ver-tex in such a way that adjacent vertices have distinct colors.Define the chromaticnumber of G as x（G）=min{k|graph G has k-colorings}.Similar,a （proper）k-edge-coloring of graph G is an assignment of one of k colors to each edge so that notwo adjacent edges have the same color.The edge-chromatic number is defined asx′（G）=min{k|graph G has k-edge-colorings}.The total coloring is a generalization of the coloring and the edge coloring.It’sa traditional coloring problem and was introduced by Vizing（1964） and indepen-dently Behzad（1965）.The tltal coloring is defined as all of vertices and edges ofthe graph are colored in such a way that no two adjacent or incident elements arecolored the same.The total chromatic number is defined as x_T（G）=min{k|G hask-TC}.On the basis of the total coloring, Zhang Zhongfu presented the conceptof the adjacent vertex-distinguishing total colorings and gave the conjecture andtwo results.The definition of asjacent vertex-distinguishing total coloring by Zhang Zhongfuis as follows: Let G（V（G）, E（G）） is a simple connected graph of which the or-der at least 2,k is a positive integer and f is a mapping from V（G）∪E（G） to {1,2,…,k}.For any u∈V（G）,if1)for any uv,vw∈E（G）,u≠w,there is f（uv）≠f（vw）.2)for any uv∈E（G）,there are f（u）≠f（v）, f（u）≠f（uv）, f（uv）≠f（v）.Then f is called a k-total coloring of graph G and the total-chromatic number isdefined as x_T（G）（or denoted as x″（G））=min{k|graph G has k-total-colorings}.Iff also satisfics3)for any uv∈E（G）,there is C（u）≠C（v）;where C（u）={f（u）}∪{f（uv）|uv∈E（G）} is called the color set of vertex u .Then f is called a k adjacent vertex-distinguishing total coloring of graph G（brieflynoted as k-AVDTC） and x_at（G）=min{k|G has k-AVDTC} is called the adjacentvertex-distinguishing total chromatic number of graph G.Zhang Zhongfu presented two importent results about the adjacent vertex-distinguishing total coloring.For any simple connected graph G of order n（n≥2）,adjacent vertex-distinguish-ing total chromatic number x_at（G） exsits,andx_at（G）≥△（G）+1.If G（V（G）, E（G）） has two adjacent maximum degree vertices,then x_at（G）≥△（G）+2.The two results about the adjacent vertex-distinguishing total coloring areright apparently.The following conjecture is proposed by Zhang Zhongfu.For any simple connected graph G of order n（n≥2）,then x_at（G）≤△（G）+3.The problem of determining the adjacent vertex-distinguishing total chro-matic number of a graph is NP-hard. In present, we obtain the adjacent vertex- distinguishing total chromatic number for special graphs such as path,cycle,completegraph,2-complete graph,star, fan,wheel,tree etc.We also obtain the adjacent vertex-distinguishing total chromatic number for the Mycielski graph,link graph,the Carte-sian product graph,Petersen graph,Heawood graph,Thomassen graph erc.The edge-coloring problem was pised in 1880 in relation with the well-knownfour-color conjecture. In 1964,Vizing proved the famous Vizing’s theorem:△（G）≤x′（G）≤△（G）+1 for any simple graph G.In 1974,R.P.Gupta studied the edge cover coloring problem.The edge covercoloring of a graph G is to color all the edges of G so that each color appears ateach vertex v at least once.The maximum positive integer k such that G has ak-edge cover-coloring is called the edge cover chromatic index of G and is denotedby x′_c（G）.A graph G is said to be of Type CI if x′_c（G）=δand of Type CⅡifx′_c（G）=δ-1.G.Liu,L.Miao and H.Song studied the edge cover coloring problemsand got many results.In 2006,L.Sun prosed the concept of the total colors maximal cliques （vertex-）coloring.A total colors maximal cliques coloring of graph G is a vertex-coloringsuch that all colors appear at each maximal clique of graph G.The maximumnumber of total colors maximal cliques coloring of G is called total colors maxi-mal cliques chromatic number and denoted by x_maxcT（G）.Apparently,x_maxcT（G）≤min{|H||H is a maximal clique of graph G}.In this thesis,the first part deals with the adjacent vertex-distinguishing to-tal chromatic number for Hajós sum of wheel,complete graph and we obtainthe adjacent vertex-distinguishing total chromatic number for graph P_n^k, flowerG.The second part focuses on the equivalence of total colors maximal cliques chro-matic number of the Lexicographic product,the Caretsian product of graph,linkgraph,the outer graph, graph K_n-N,graph （?）_n, Mycielski graph,similar Mycielskigraph.We briefly summerize our main results as follow: Let G₁ and G₂ be vertex disjoint graphs,containing edges x₁y₁∈E（G₁） andx₁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 identifying x₁ and x₂,deletingthe edge x₁y₁, x₂y₂,and adding the edge y₁y₂.Let W_n=K₁∨C_n, V（W_n）={v₁, v₂,..., v_n, V₀}, E（W_n）={v_iv_i+1|i=1, 2,...,n; v_n+1=v₁}∪{v₀v_i[i=1, 2,..., n}, W’_n is the copy of W_n.Theorem 2.1.1 Hajós sum W^*_n=（W_n, v₁v₂）+（W’_n, v’₁v’₂） identifies v₁ andv’₁ as v₁, thenTheorem 2.1.2 Hajōs sum G=（W_n, v₀v₁）+（W’_n,v’₀v’₁） identifies v₀ andv’₀ as v₀, then Xat（G）=2n-1.Theorem 2.1.3 Hajòs sum G=（K_m,v₁v₂）+（K_n, v’₁v’₂） identifies v₁ andv’₁ as v₁, thenGraph P_n is a path which the order is n.Graph P^k_n is obtained from addingan edge to graph P_n if and only if the distance of two vertices is k.Theorem 2.2.1 For graph P^k_n,k=「n/2」,there is Xat（P^k_n）=5.Graph K_n is a complete graph which the vertices is v₁, v₂,..., v_n.Flower G isobtained from adding the vertices v_i1, v_i2,..., v_im, to the vertice v_i of K_n, linkingthe vertices v_i1, v_i2,..., v_imi, to the path v_i1v_i2..., v_imi.Theorem 2.2.2 For flower G,let m_s=max_k=1,2,...,n m_k,then For any graph G,it’s line graph L（G） is defined as:vertex set is E（G）,thereis an edge in two vertices of graph L（G） if and only if two edges are adjacent ingraph G.For any graph G,it’s total graph T（G） is defined as:vertex set is V（G）∪E（G）,there is an edge in two elements of graph T（G） if and only if two elementsare adjacent or incident in graph G.Let p=min{|G’||G’ is a maximal clique of graph G}, q=min{[H’||H’ is amaximal clique of graph H}.Theorem 3.1.1 If graph G is the line graph of H and p≥4,then the to-tal colors maximal cliques coloring of G and the edge covered coloring of H areequivalent.Corollary 3.1.2 Gupta’s theorem is equivalent to two cases as follow:（1） If G is the line graph of H and p≥4,then p-1≤XmaxcT（G）≤P.（2） If G is the total graph of H and p≥4,then p-1≤XmaxcT（G）≤P.M is the match of the complete graph K_n,then all maximal cliques’ numberof K_n-M is same and is n-2|M|+|M|=n-|M|.The vertex set of any maxi-mal clique of K_n-M is the union of V（K_n）\V（M） and the vertices which areobtained from the match edges of M.Theorem 3.1.3 For the complete graph K_n, N（?）E（K_n） andδ（K_n-N）≥n-2,then XmaxcT（K_n-N）=n-|N|.Theorem 3.1.4 If G=（?）_n,thenThe link graph G∨H of graph G and graph H is defined as follow: V（G∨H）=V（G）∪V（H）, E（G∨H）=E（G）∪E（H）∪{uv|u∈V（G）, v∈V（H）}. Theorem 3.1.5 For any simple connected graph G,H,then XmaxcT（G∨H）=XmaxcT（G）+XmaxcT（H）.The Lexicographic product graph G[H] of graph G and graph H is definedto be a graph with V（G[H]）=V（G）×V（H） and E（G[H]）={（a,x）（b,y）|ab∈E（G） or a=b and xy∈E（H）}.Theorem 3.1.6 If graph G,H satisfy XmaxcT（G）=p, XmaxcT（H）=q, thenXmax（?）T（G[H]）=XmaxcT（G）XmaxcT（H）.Not all graph G, H satisfies XmaxcT（G[H]）=XmaxcT（G）XmaxcT（H）.For example: G=P_n, H=C_2m+1, but XmaxcT（G[H]）=3≠2×1.For graphs G₁=（V₁, E₁） and G₂=（V₂, E₂）,the Cartesian product graphG₁×G₂] has vertex set V₁×V₂ and in which （v₁, u₁） is adjacent to （v₂, u₂） if andonly if either v₁v₂∈E₁ and u₁=u₂∈V₂ or v₁=v₂∈V₁ and u₁u₂∈E₂.Theorem 3.1.7 If p-1≤XmaxcT（G）≤p, q-1≤XmaxcT（H）≤q, thenXmaxcT（G×H）=min{XmaxcT（G）. XmaxcT（H）}.We call the graph obtained by the Mycielski Construction the Mycielskigraph. Given a graph G with V（G）={v₁, v₂,..., v_n},the Mycielski graph （de-noted by M（G）） of G is defined to be a graph with V（M（G））=V∪{v’₁, v’₂,..., v’_n,ω} and E（M（G））=E（G）∪{v_iv’_j[v_iv_j∈E（G）,i,j=1,..., n}∪{v’_iω|i=1,..., n}.Theorem 3.2.1 For any simple connected graph G,there is XmaxcT（M（G））=1.Theorem 3.2.2 For any simple connected graph G, let u（G）=M（G）-ω.there is XmaxcT（u（G））=XmaxcT（G）.Given a graph G with V（G）={v₁, v₂,..., v_n}, the similar Mycielski graph （denoted by S（G）） of G is defined to be a graph with V（S（G））=V（G）∪V（G’）∪{w},G’is the copy of graph G and E（S（G））=E（G）∪E（G’）∪{v_iv’_i|v_i∈V（G）,i=1.2,..., n}∪{v_iv’_j|v_iv_j∈E（G）,i,j=1,2,...,n}∪{v’_iw|i=1.2,..., n}.Graph S_m（G） is defined as follow: S₁（G）=S（G）.V（S_m（C））=V（C）∪V（G’）∪V（G"）∪...∪V(G^（m）)∪{w}, E（S_m（C））=E（C）∪E（C’）∪E（C"）∪...∪E(G^（m）)∪{v_i^（j）v_i^（j+1）|v_i∈V（G）,i=1,2,...,n;j=0, 1,...,m-1;v_i^（0）=v_i}∪(v_i^（k）v_j^（k+1）|v_iv_j∈E（C）,i,j=1,2,..., n; k=0, 1,..., m-1}∪{v_i^（m）|v_i∈V（G）, i=1, 2,..., n}.Theorem 3.2.3 For any simple connected graph G, there is XmaxcT（S（G））=XmaxcT（G）+1.Corollary 3.2.4 If S₀（G）=G∨{w},then XmaxcT（S₀（G））=XmaxcT（G）+1.Theorem 3.2.5 For any simple connected graph G, there is XmaxcT（S_m（G））=xmaxcT（G）+1.Theorem 3.2.6 If C is an outer planar graph and p=2.thenTheorem 3.2.7 If G is an outer planar graph and p=3. then XmaxcT（G）=3.更多还原