【作者】 王颜妮；

【导师】 孙磊；

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

【摘要】 染色问题是图论研究的经典领域，它源自四色定理的研究，是图论研究中一个很活跃的课题．另外染色问题在组合分析和实际生活中有着广泛的应用，因此各类染色问题被相继提出并加以发展、应用．图G的一个（正常）k-染色是将k种颜色分配给G的顶点集V（G），使得相邻两顶点的颜色不同．定义色数为：X（G）=min{k|图G有k-染色}．类似地，图G的一个（正常）k-边染色是将k种颜色分配给G的边集E（G），使得有公共端点的两边的颜色不同．边色数X’（G）=min{k|图G有k-边染色}．图的全染色的概念是对点染色和边染色的推广，是对图的所有元素（顶点和边）都进行染色，使得相邻或关联的两元素颜色不同．图的全色数XT（G）=min{k|图G有k-全染色)．全染色是图论染色的一个传统问题，由Vizing（1964）[1]和Behzad（1965）[2,3]各自独立提出的，同时分别给出全染色猜想．邻点可区别的全染色的概念是图的一正常的全染色且任相邻顶点的色集不同，由张忠辅[4]在全染色的基础上提出的，并同时给出了相应的猜想和两个引理．用Xat（G）表示图G的邻点可区别的全色数．超图是一般图的一个重要推广，超图的染色问题也是图的染色问题的推广．1966年Behzad首次开始超图染色的研究，逐渐地将染色理论引入到超图中来．超图的全染色的概念是图的全染色概念的一个自然推广．王维凡，张克民在[5]中给出了超图全染色的概念，分为弱全染色和强全染色两种．超图H=（V,E）的弱（强）全染色是对超图的所有元素（顶点和超边）都将进行染色，使得顶点是弱（强）染色，边是强边染色，并且任意关联的顶点和超边的颜色不同．超图的弱（强）全色数X_T^W（H）=min{k|超图H有弱k-全染色}（X_K^S（H）=min{k|超图H有强k-全染色}）．图的分数染色的概念是从图染色的分数推广的角度提出的．E．Scheinerman和D．Ullman在[6]中提出了分数染色的概念，并指出确定一个图的分数色数是NP-困难的．用Xf（G）表示图G的分数色数．在本文中，我们主要得到结论如下：首先给出了m-Mycielski图和类m-Mycielski图在全染色、邻点可区别全染色的几个相关的结论．定义2．1．1给定图G，顶点集V⁰={u₁⁰,u₂⁰,…u_n⁰},边集E⁰，整数m≥1，图G的m-Mycielski图记为μ_m（G）定义为：顶点集V（μ_m（G））：V⁰∪V¹∪V²∪…∪V^m∪{ω}，其中Vⁱ={v_jⁱ|v_j⁰∈V⁰}，i=1，2，…，m为V⁰的第i个复制，边集E（μ_m（G））=E⁰∪（?）．其中μ₁（G）为图G的Mycielski图[8]．定理2．1．1设G为n阶非空图，整数m≥1．（a）m为奇数时．若XT（G）≥n，则XT（μ_m（G））≤XT（G）+△（G）；若XT（C）<n，则XT（μ_m（G））≤n+△（G）．（b）m为偶数时．若XT（G）≥n+1，则XT（μ_m（G））≤XT（G）+n；若XT（G）<n+1，则XT（μ_m（G））≤XT（G）+n+1．由定理2．1．1可推出当m为奇数时，μ_m（G）满足全染色猜想及其达到全色数下界的一些充分条件（推论2．1．2-推论2．1．3）．定理2．1．4设G为δ（G）≥2的n阶图，整数m≥1．（a）m为奇数时．若X_at（G）≥n，则X_at（μ_m（G））≤X_at（G）+△（G）；若X_at（G）<n，则X_at（μ_m（G））≤n+△（G）．（b）m为偶数时．若X_at（G）≥n+1，则X_at（μ_m（G））≤X_at（G）+n；若X_at（G）<n+1，则X_at（μ_m（G））≤X_at（G）+n+1．由定理2．1．4可推出当m为奇数时，μ_m（G）满足邻点可区别全染色猜想及其达到邻点可区别全色数下界的一些充分条件（推论2．1．5-推论2．1．6）．定义2．1．2给定图G，顶点集V⁰={V₁⁰，V₂⁰，…，V_n⁰}，边集E⁰，整数m≥1．令图G的m-1个复制图记为Gⁱ，i=1，2，…，m-1，其中Gⁱ的顶点集记为Vⁱ={v_jⁱ|v_j⁰∈V⁰}，边集记为Eⁱ={v_jⁱv_jⁱ,|v_j⁰v_j⁰,∈E⁰)．顶点集V⁰的另一个复制记为V^m={v_j^m|v_j⁰∈V⁰}．图G的类m-Mycielski图记为μ’_m（G）定义为：顶点集V（μ’_m（G））=（?），边集其中若m=1，则μ’₁（G）=μ₁（G）即为Mycielski图[8]．定理2．1．7设G为n阶非空图，整数m≥2．若XT（G）≥n-△（G），则XT（μ’_m（G））≤XT（C）+2△（G）；若XT（G）<n-△（G），则XT（μ’_m（G））≤n+△（G）．由定理2．1．7可推出μ’_m（G）满足全染色猜想及其达到全色数下界的一些充分条件（推论2．1．8-推论2．1．9）．定理2．1．10设G为δ（G）≥2的n阶图，整数m≥2．若X_at（G）≥n-△（G），则X_at（μ’_m（G））≤X_at（G）+2△（G）；若X_at（G）<n-△（G），则X_at（μ’_m（G））≤m+△（G）．由定理2．1．10可推出μ’_m（G）满足邻点可区别全染色猜想及其达到邻点可区别全色数下界的一些充分条件（推论2．1．11-推论2．1．12）．下面四个结论主要给出了推广的两类双钻图及两一般轮的Hajos sum的邻点可区别的全色数．定义2．2．1若图G=（V,E），其中V（G）={v₀,v₁，….v_2n，u₁，u₂}，E（G）=}v₀v_i|i= 1,2,…，2n)∪(viv_i+1+1|i=1,2,…，2n-1}∪{u_2nv₁)∪{v₁v_i|i=1，2，…，n+1)∪{u₂v_i|i= n+1，n+2，…，2n，1}，n≥3，则称图G为推广后的第一类双钻图．特别地，n=3为一般的双钻图[9].定义2．2．2若图G=（V,E）；其中V（G）=(v₀,v₁…,v_n，v’₀,v’₂,…，u’_n-1,v₀,v’₀}，（?）1,2，…,n;v’₁=v₁,v’_n=v_n}，n≥4，则称图G为推广后的第二类双钻图．特别地，n=4为一般的双钻图[9]．定理2．2．1-定理2．2．2分别给出了这推广的两类双钻图的邻点可区别全色数．定义2．2．3两个点不交的图G₁和G₂的Hajos sumG=（G1，x₁y₁）+（G2，x₂y₂），是由G₁∩G₂粘合x₁,x₂为一个点，删去边x₁y₁,x₂yv2增加边y₁y₂所得，其中x₁y₁∈E（G₁），x₂y₂∈E（G₂）．令．定理2．2．3-定理2．2．4分别给出了两轮的辐边及其轮边作Hajos sum的邻点可区别全色数．下面主要给出了超图中超双星的弱全染色和强全染色以及有关全色数计数的两个相关结论．定义2．3．1中心点是v的超星是满足下列条件的一簇S（v）．（1）E∈S（v）（?）|E|≥2．（2）E，E’∈S（v）（?）E∩E’={v}．定义2．3．2如上面定义的两超星S（v），S（v）．超星S（v）中心点v的度数为d（v），与v关联的超边为E_i（i=1，2，…，d（v））．超星S（u）中心点u的度数为d（u），与u关联的超边为局，E₁,E’_i（i=2，3，…,d（u））．其中E_i（i=2，3…，d（v））与E’_i（i=2,3…，d（u））互不相交，E₁为超星S（v）与S（u）仅有的一条公共超边，则由这两个超星导出的子图称为超双星，记为S_v，u，其中v，u称为超双星的中心，r_i=|E_i|（i=1，2,…，d（v）），r’_i=|E’_i|（i=2，3，…，d（u）），△=max{d（v），d（u）}．定理2．3．1设S（v,u）是超双星，则弱全色数X_T^W（S（v,u））=△+1．使用△+1种颜色的不同的染色方式有N_W(（S（v,u））=（?）．定理2．3．2设S（u，u）是超双星，则强全色数X_T^S（S（v,u））=M+1．使用M+1种颜色的不同的染色方式有N_S(（S（v,u））=（?），其中M=下面几个结论是关于复合图的两类子图的分数染色的．定义3．1．1对于图G和H，设V（G）={u₁,u₂,…,u_m}，V（H）={v₁,v₂,…，v_n}．它们的复合图G|H|定义为：（?）或i=k,v_jv_l∈E（H）}．定义3．1．2复合图G[H]的一类子图，记为G[H}₁，定义为：V（G[H]₁）=V（G[H]），E（G[H]₁）={（u_i，v_j）（u_k,v_l）|j=l，u_iu_k∈E（G）或v_jv_l∈E（H），u_iu_k∈E（G）或i=k，v_jv_l∈E（H）}．易知G[H]₁为G[H]的子图．特别地，当H为完全图时，G[H]+1=G[H].定义3．1．3复合图G[H]的另一类子图，记为G[H]₂，定义为：V（G[H]₂）=V（G[H]），E（G[H]₂）={（u_i，v_j）（u_k,v_l）|v_jv_l∈E（H），u_iu_k∈E（G）或i=k，v_jv_l∈E（H）}．引理3．1．1设G，H为两个图，则Xf（G[H]）=Xf（G）Xf（H）．引理3．1．2若G为长为2的路P₂，则P₂[H]₁中的任意独立集I都对应于图H的一独立集I’．定理3．1．3设G，H为两个图，则（?），其中α（G）为图G的最大独立数．特别地，若图G为点传递图，则Xf（G[H]₁）=Xf（G）Xf（H）．下面的定理3．1．4-定理3．1．7，分别证明了当图G为路，偶轮，扇，完全r部图时，Xf（G[H]₁）=Xf（G）Xf（H）=Xf（G[H]）．定理3．1．8设G，H为两个图，则Xf（G[H]₂）=Xf（H）．下面两个结论是关于两类推广的Hajos sum构造的分数色数上下界的．定义3．2．1给m（m≥3）个图G₀，G₁,…，G_m-1,对i=0，1，…，m-1，令e_i=v_iv_i+1∈G_i，设C_m=c₀c₁…c_m-1为长是m的圈，构造新图：（1）删去e_i，i=0，1,…，m-1．（2）合并所有的v_i成一个点x．（3）将u_i+1与c_i合成一个点，i=0，1，…，m-1（i+1中的加法取模m）．令此图为S₁(G₀,e₀，G₁，e₁，…,G_m-1,e_m-1)，简记为S₁．若给定m（m≥3）个图G_i=K_ni，i=1，2,…，m,则S₁(G₀，e₀，G1l，e1,…，G_m-1,e_m-1)=S₁(K_n1，e₁，K_n2，e₂，…,K_nm,e_m)，简记为S’_i．定理3．2．1对上述S’₁有（?）特别地，若n_i=n,i=1，2,…，m，则Xf（S’₁）=n-1/Xf（C_m）．定义3．2．2给n个图G₀,G₁，…G_n-1,对i=0，1,…，n-1，令e_i=x_iy_i∈E（G_i），构造新图：（1）删去e_i，i=0，1，…，n-1．（2）将y_i与x_i+1合成一个点，i=0，1，…，n-1（i+1中的加法取模n）．（3）连接边x_i与x_i+2,i=0，1,…，n-1（i+2中的加法取模n）．（4）增加点u并连接点u与x_i,i=0,1，…，n-1．令此图为S₂(G₀,e₀，G₁，e₁，…，G_n-1,e_n-1，简记为S₂．定义3．2．3对上述定义3．2．2，只将条件（3）改为（3）’连接边x_i与X_i+3，i=0，1，…，n-1（i+3中的加法取模n）．令此图为S’₂(G₀,e₀，G₁，e₁,…,G_n-1,e_n-1)，简记为S’₂．定理3．2．2 S’₂为上述图，有（?）更多还原

【Abstract】 The coloring problem is one of primary fields in the study of graph theories.It is from the the study of the celebrated four color problem. In the combinatorial mathematics and our living, the coloring problem has a big application,so with the development of the field some scholars presented and studied a few coloring problem with different restriction.A （proper）k-coloring of graph G is an assignment of one of k colors to each vertex in such a way that adjacent vertices have distinct colors.Define the chromatic number 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 no two adjacent edges have the same color.The edge-chromatic number is defined as X’（G） = min{k|graph G has k-edge-colorings}.The total coloring is a generalization of the coloring and the edge coloring, all of the elements （vertices and edges） of the graph are colored in such a way that no two adjacent or incident elements are colored the same.The total chromatic number is denned as XT（G）= min{k|graph G has k- total colorings}.It’s a traditionalcoloring problem and was independently introduced by Vizing（1964）[1] and Behzad（ 1965） [2,3] with total coloring conjecture.The adjacent vertex-distinguishing total coloring is a total coloring and any adjacent vertices have distinct color set. It’s presented by Zhongfu Zhang[4] on the basis of the total coloring,with the conjecture and two lemmas.The adjacent vertex-distinguishing total chromatic number of G is denoted by X_at（G）. Hypergraph is an important generalization of graph.the coloring problem of hypergraph is also a generalization of the coloring problem.Behzad first studied the coloring problem of hypergraph in 1966, The coloring theories led into the hypergraph in gradually. The total coloring of hypergraph is the natural generalization of the total coloring.It was introduced by Weifan Wang and Kemen Zhang in [5],it contain weak total coloring and strong total coloring.A weak（strong,resp.） total coloring of hypergraph H = （V, E） is that all of the elements（vetices.hyperedges） of hypergraph are colored in such a way that vertices are weak（strong,resp.） coloring, edges are strong edge-coloring.Define weak（strong,resp.） total chromatic number of H as X_T^W（H） = min{k|hypergraph H has weak k-total-colorings}（X_T^S （H） = min{k|hypergraph H has strong k-total-colorings},resp.）.The definition of fractional coloring of graph is fractional generalization of the coloring.It was given by E.Scheinerman and D.Ullman in [6],with determining the fractional chromatic number of a graph is NP-hard. The fractional chromatic number of G is denoted by Xf（G）.We briefly summerize our main results as follow:We firstly obtain several results about the total coloring and the adjacent vertex- distinguish total coloring of m-Mycielski graphs and similar m-Mycielski graphs.Definition 2.1.1 Given a graph G.with vertex set V⁰={u₁⁰,u₂⁰,…u_n⁰},edge set E⁰,given an integer m≥1.The m-Mycielskian of G,denoted byμ_m（G）,with vertex set V（μ_m{G）) = V⁰∪V¹∪V²∪…∪V^m∪{ω}, where Vⁱ = {v_jⁱ|v_j⁰∈V⁰} is i - th distinct copy of V⁰ for i = 1,2,…, m, edge set E（μ_m（G）） = E⁰∪（?）whereμ₁（G） is Mycielskian[8] of G.Theorem 2.1.1 Suppose G is a nonemperty graph with n vertices,given an integer m≥1.（a） When m is odd.If XT（G）≥n,then XT（μ_m（G））≤XT（G）+△（G）;If XT（G）<n,then XT（μ_m（G））≤n+△（G）（b） When m is even.If XT（G）≥n+1,then XT（μ_m（G））≤XT（G）+n; If XT（G） <n + 1,then XT（μ_m（G））≤XT（G） + n+1.By Theorem 2.1.1,we can deduct some sufficient conditions thatμ_m（G） satisfiesthe total coloring conjecture and reaches the lower bound of the total chromatic number when m is odd （Corollary 2.1.2-Corollary 2.1.3）.Theorem 2.1.4 Suppose G is a graph with n vertices andδ（G）≥2, given an integer m≥1.（a） When m is odd.If X_at（G）≥n,then X_at（μ_m（G））≤X_at（G） +△（G）; If X_at（G） < n,then X_at（μ_m（G））≤n +△（G）.（b） When m is even.If X_at（G）≥n + 1,then X_at（μ_m（G））≤X_at（G） + n; If X_at（G） < n + 1,then X_at（μ_m（G））≤X_at（G） + n + 1.By Theorem 2.1.4,we can. deduct some sufficient conditions thatμ_m（G） satisfies the adjacent vertex-distinguishing total coloring conjecture and reaches the lower bound of the adjacent vertex-distinguishing total chromatic number when m is odd （Corollary 2.1.5-Corollary 2.1.6）.Definition 2.1.2 Given a graph G,with vertex set V⁰ = {u₁⁰,u₂⁰,…,u_n⁰},edge set E⁰,given an integer m≥1. Where m - 1 copy graphs of G,denoted by Gⁱ for i = 1,2,…,m -1,and graph Gⁱ with vertex set Vⁱ = {v_jⁱ|v_j⁰∈V⁰},edge set Eⁱ={v_jⁱv_j’ⁱ|v_j⁰v_j’⁰∈E⁰}.Another copy of V⁰,denoted by V^m = {v_j^m|v_j⁰∈V⁰}. Similarm - Mycielskian of G,denoted byμ’_m（G） with vertex set V（μ’_m（G）） = （?）{ω},edge set E（μ’_m（G））=（?）where if m = 1,thenμ’₁（G） =μ₁（G） is Mycielskian[8].Theorem 2.1.7 Suppose G is a nonemperty graph with n vertices,given an integer m≥2.If XT（G）≥n-△（G）, then XT（μ’_m（G））≤XT（C）+2△（G）; If XT（G）<n-△（G）,then XT（μ’_m（G））≤n+△（G）.By Theorem 2.1.7,we can deduct some sufficient conditions thatμ’_m（G） satisfiesthe total coloring conjecture and reaches the lower bound of the total chromatic number （Corollary 2.1.8-Corollary 2.1.9）.Theorem 2.1.10 Suppose G is a graph with n vertices andδ（G）≥2, given an integer m≥2.If X_at（G）≥n-△（G）,then X_at（μ’_m（G））≤X_at（G）+2△（G）;If X_at（G）<n-△（G）,then X_at（μ’_m（G））≤n+△（G）.By Theorem 2.1.10,we can deduct some sufficient conditions thatμ’_m（G） satisfies the adjacent vertex-distinguishing total coloring conjecture and reaches the lower bound of the adjacent vertex-distinguishing total chromatic number （Corollary 2.1.11-Corollary 2.1.12）.The following four results obtain the adjacent vertex-distinguish total chromatic number of two kinds of double diamond graph and Hajos sum, of wheels.Definition 2.2.1 If a graph G = （V, E） with vertex set V（G） = {v₀,v₁,…,v_2n,u₁,u₂}, edge set E（G） = {v₀v_i|i=1,2,…,2n)∪(v_iv_i+1|i=1,2,…,2n-1}∪{u_2nv₁)∪{v₁v_i|i=1,2,…,n+1)∪{u₂v_i|i= n+1,n+2,…,2n,1},for n≥3, thengraph G is the generalization of the first type double diamond graph. Especially,if n = 3,then G is the first type double diamond graph[9].Definition 2.2.2 If a graph G = （V, E） with vertex set V（G） = (v₀,v₁…,v_n，v’₀,v’₂,…，u’_n-1,v₀,v’₀},edge set E（G） = {v₀v_i|i=1,2,…,n}∪{v_iv_i+1|i=1,2,…,n-1}∪{v_nv₁}∪{u₀v_i}i=1,2,…,n}∪{v’₀v’_i|i=1,2,…,n;v’₁=v₁,v’_n=v_n}∪{v’_iv’_i+1|i=1,2,…,n-1;v’₁=v₁,v’_n=v_n}∪{u’₀v’_i|i=1,2,…,n;v’₁=v₁,v’_n = v_n}, for n≥4,then graph G is the generalization of the second type double diamond graph. Especially,if n = 4,then G is the second type double diamond graph [9].The following Theorem 2.2.1-Theorem 2.2.2 respectively obtain the adjacent vertex-distinguish total chromatic number of generalization of two types double diamond.Definition 2.2.3 Let G₁ and G₂ be vertex disjoint graphs,the Hajos sum G =（G1,x₁y₁）+（G2,x₂y₂） is obtained from G₁∪G₂ by identifying x₁ and x₂, deleting the edge x₁y₁,x₂y₂,and adding the edge y₁y₂, where x₁y₁∈E（G₁）,x₂y₂∈E（G₂）.Let W_n=K₁∨C_n,V（W_n）={v₀,v₁…,v_n},E（W_n）={v_iv_i+1|i=1,2…,n;v_n+1=v₁}∪{v₀v_i|i=1,2,…,n}.W-m=K₁∨C_m,V（W_m）={v’₀,v’₁,…,v’_m},E（W_m）={v’_iv’_i+1|i=1,2,…,m;v’_m+1=v’₁}∪{v’₀v’_i|i=1,2,…,m}.The following Theorem 2.2.3-Theorem 2.2.4 respectively obtain the adjacent vertex-distinguish total chromatic number of Hajos sum of spoke edges and wheel edges of two wheels.The following we obtain two results about the weak（strong,resp.） total chromatic number of double hyperstar and total chromatic number enumeration.Definition 2.3.1 Hyperstar with central vertex v is a set S（v） which satisfies the follow conditions.（1） If E∈S（v） then |E|≥2.（2） If E, E’∈S（v） then E∩E’ = {v}.Definition 2.3.2 As above definition of two hyperstars S（v） and S（u）. The degree of hyperstar S（v） with central vertex v is d（v）, incident hyperstar with v is E_i（i = 1,2,…,d（v））.The degree of hyperstar S（u） with central vertex u is d（u）,incident hyperstar with u is E₁.E’₁（i= 2,3…, d（u））,where E_i（i = 2,3…, d（v）） and E’_i（i = 2,3…, d（u）） are disjoint each other, E₁ is the only common hyperedge of hyperstar S（v） and S（u）,then the defination of double hyperstar is the resulted subergraph by this two hyperstars.denoted by S（v, u）, where v and u is the central of double hyperstar.r_i = |E_i|（i = 1,2,…,d（v））,r’_i = |E’_i|（i= 2,3,…, d（u））,△= max{d（v）, d（u）}.Theorem 2.3.1 Suppose S（v,u） is double hyperstar,then weak total chromatic number X_T^W（S（v,u））=△+1.Different ways of the coloring with△+1 colors have N_W(（S（v,u））=（?）.Theorem 2.3.2 Suppose S（v, u） is double hyperstar,then strong total chromatic number X_T^S（S（v,u））=M+1.Different ways of the coloring with M + 1 colors have N_S(（S（v,u））=（?）. Where M = max{m₁, m₂,△},m₁=max{r_i|i=1,2…,d（v）},m₂=max(r’_i|i=2,…,d（u）}.The following several results are about the fractional coloring of two kinds of subgraph of lexicographic product graph.Definition 3.1.1 For graphs G and H,suppose vertex set V（G） = {u₁,u₂,…,u_m}, V（H） ={v₁,v₂,…,v_n}. The lexicographic product graph G[H] of them is defined to be a graph with vertex set V（G[H]） = V（G）×V（H） = {（u_i,v_j）|1≤i≤m, 1≤j≤n},edge set E（G[H]） = {（u_i, v_j）（u_k,v_l）|u_iu_k∈E（G） or i = k, v_jv_l∈ E（H）}.Definition 3.1.2 A kind of subgraph of the lexicographic product graph G[H] is denoted by G[H]₁ with vertex set K（G[H]₁） = V（G[H]）,edge set E（G[H]₁） = {（u_i,v_j）（u_k,v_l）|j=l,u_iu_k∈E（G） or v_jv_l∈E（H）,u_iu_k∈E（G）or i=k,v_jv_l∈E（H）}.It’s known that G[H]₁ is subgraph of G[H].Especially,if H is complete graph,thenG[H]₁=G[H].Definition 3.1.3 Another kind of subgraph of the lexicographic product graph G[H] is denoted by G[H]₂ with vertex set V（G[H]₂） = V（G[H]）,edge set E（G[H]₂）={（u_i,v_j）（u_k,v_l）|v_jv_l∈E（H）,u_iu_k∈E（G）or i=k,v_jv_l∈E（H）}.Lemma 3.1.1 Suppose G and H are two graphs,then Xf（G[H]） = Xf（G）Xf（H）.Lemma 3.1.2 If G is a path P₂ of length 2,then any independent set I of P₂[H]₁ correspond to an independent set I’ of H.Theorem 3.1.3 Suppose G and H are two graphs,then |V（G）|/α（G）XF（H）≤Xf（G[H]₁）≤Xf（G）Xf（H）,whereα（G） is maximum independent number of graph G. Especially, if graph G is vertex transfer graph,then Xf（G[H]₁）=Xf（G）Xf（H）.The following Theorem 3.1.4-Theorem 3.1.7 respectively obtain Xf（G[H]₁） Xf（G）Xf（H）=Xf（G[H]） when G is path.fan.even wheel.complete r-partite graph.Theorem 3.1.8 Suppose G and H are two graphs,then Xf（G[H]₂）=Xf（H）.The following two results are about the upper（lower） bound about the fractional chromatic number of two kinds of generalization of Hajos sum.Definition 3.2.1 Given m（m≥3） graphs G₀,G₁,…,G_m-1,for i = 0,1,…, m -1,let e_i=v_iv_i+1∈G_i,C_m=c₀c₁…c_m-1 be a cycle of length m,construct a new graph as following:（1） Delete the edges e_i for i = 0,1,…, m, - 1.（2） Identify all the v_i into a single vertex and name x.（3） Identify v_i+1 and c_i for i = 0,1,…, m - 1（the addition of i + 1 is modulo m）.We shall denote the resulting graph by S₁ (G₀, e₀, G₁, e₁,…, G_m-1, e_m-1), simply by S₁.If given m（m≥3） graphs G_i = K_ni for i = 1,2,…, m,then S₁(G₀,e₀,G₁,e₁,…,G_m-1,e_m-1) = S₁(K_n1,e₁,K_n2,e₂,…,K_nm,e_m), simply by S’₁.Theorem 3.2.1 For above S’₁,then （?）Especially,if n_i = n,i = 1,2,…,m,then X_f（S’₁） =n-1/Xf（C_m）.Definition 3.2.2 Given n graphs G₀,G₁,…G_n-1,for i = 0,1,…, n-1, let e_i = x_iy_i∈G_i, construct a new graph as following:（1） Delete e_i for i = 0,1,…,n-1.（2） Identify y_i and x_i+1 for i = 0,1,…, n - 1（the addition of i+1 is modulo n）.（3） Add edges to connect x_i and x_i+2 for i = 0,1,…, n -1（the addition of i + 2 is modulo n）.（4） Add a vertex u and connect u to x_i for i = 0,1,…, n-1.We shall denote the resulting graph by S₂(G₀,e₀,G₁,e₁,…,G_n-1,e_n-1,simply by S₂.Definition 3.2.3 For above Definition 3.2.2,only condition （3） substitute being（3）’ Add edges to connect x_i and x_i+3 for i= 0,1,…, n - 1（the addition of i + 3 is modulo n）.We shall denote the resulting graph by S’₂(G₀,e₀,G₁,e₁,…,G_n-1,e_n-1), simply by S’₂.Theorem 3.2.2 If S’₂ is above graph,then max{X_f（G_i）|i = 0,1,…, n-1}-1≤X_f（S’₂）≤max{Xf（G_i）|i = 0,1,…, n - 1} + 1.更多还原