图的全染色、邻点可区别全染色及分数染色
|
摘要
染色问题是图论研究的经典领域，它源自四色定理的研究，是图论研究中一个很活跃的课题．另外染色问题在组合分析和实际生活中有着广泛的应用，因此各类染色问题被相继提出并加以发展、应用．
图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~0={u_1~0,u_2~0,…u_n~0},边集E~0，整数m≥1，图G的m-Mycielski图记为μ_m(G)定义为：顶点集V(μ_m(G))：V~0∪V~1∪V~2∪…∪V~m∪{ω}，其中V~i={v_j~i|v_j~0∈V~0}，i=1，2，…，m为V~0的第i个复制，边集E(μ_m(G))=E~0∪(?)．
其中μ_1(G)为图G的Mycielski图[8]．
定理2．1．1设G为n阶非空图，整数m≥1．
(a)m为奇数时．若XT(G)≥n，则XT(μ_m(G))≤XT(G)+△(G)；若XT(C) (b)m为偶数时．若XT(G)≥n+1，则XT(μ_m(G))≤XT(G)+n；若XT(G) 由定理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) (b)m为偶数时．若X_(at)(G)≥n+1，则X_(at)(μ_m(G))≤X_(at)(G)+n；若X_(at)(G) 由定理2．1．4可推出当m为奇数时，μ_m(G)满足邻点可区别全染色猜想及其达到邻点可区别全色数下界的一些充分条件(推论2．1．5-推论2．1．6)．
定义2．1．2给定图G，顶点集V~0={V_1~0，V_2~0，…，V_n~0}，边集E~0，整数m≥1．令图G的m-1个复制图记为G~i，i=1，2，…，m-1，其中G~i的顶点集记为V~i={v_j~i|v_j~0∈V~0}，边集记为E~i={v_j~iv_j~i,|v_j~0v_j~0,∈E~0)．顶点集V~0的另一个复制记为V~m={v_j~m|v_j~0∈V~0}．图G的类m-Mycielski图记为μ'_m(G)定义为：顶点集V(μ'_m(G))=(?)，边集
其中若m=1，则μ'_1(G)=μ_1(G)即为Mycielski图[8]．
定理2．1．7设G为n阶非空图，整数m≥2．若XT(G)≥n-△(G)，则XT(μ'_m(G))≤XT(C)+2△(G)；若XT(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) 由定理2．1．10可推出μ'_m(G)满足邻点可区别全染色猜想及其达到邻点可区别全色数下界的一些充分条件(推论2．1．11-推论2．1．12)．
下面四个结论主要给出了推广的两类双钻图及两一般轮的Hajos sum的邻点可区别的全色数．
定义2．2．1若图G=(V,E)，其中V(G)={v_0,v_1，….v_(2n)，u_1，u_2}，E(G)=}v_0v_i|i= 1,2,…，2n)∪(viv_(i+1)+1|i=1,2,…，2n-1}∪{u_(2n)v_1)∪{v_1v_i|i=1，2，…，n+1)∪{u_2v_i|i= n+1，n+2，…，2n，1}，n≥3，则称图G为推广后的第一类双钻图．特别地，n=3为一般的双钻图[9].
定义2．2．2若图G=(V,E)；其中V(G)=(v_0,v_1…,v_n，v'_0,v'_2,…，u'_(n-1),v_0,v'_0}，(?)1,2，…,n;v'_1=v_1,v'_n=v_n}，n≥4，则称图G为推广后的第二类双钻图．特别地，n=4为一般的双钻图[9]．
定理2．2．1-定理2．2．2分别给出了这推广的两类双钻图的邻点可区别全色数．
定义2．2．3两个点不交的图G_1和G_2的Hajos sumG=(G1，x_1y_1)+(G2，x_2y_2)，是由G_1∩G_2粘合x_1,x_2为一个点，删去边x_1y_1,x_2yv2增加边y_1y_2所得，其中x_1y_1∈E(G_1)，x_2y_2∈E(G_2)．令．
定理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_1,E'_i(i=2，3，…,d(u))．其中E_i(i=2，3…，d(v))与E'_i(i=2,3…，d(u))互不相交，E_1为超星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_1,u_2,…,u_m}，V(H)={v_1,v_2,…，v_n}．它们的复合图G|H|定义为：(?)或i=k,v_jv_l∈E(H)}．
定义3．1．2复合图G[H]的一类子图，记为G[H}_1，定义为：V(G[H]_1)=V(G[H])，E(G[H]_1)={(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]_1为G[H]的子图．特别地，当H为完全图时，G[H]+1=G[H].
定义3．1．3复合图G[H]的另一类子图，记为G[H]_2，定义为：V(G[H]_2)=V(G[H])，E(G[H]_2)={(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_2，则P_2[H]_1中的任意独立集I都对应于图H的一独立集I'．
定理3．1．3设G，H为两个图，则(?)，其中α(G)为图G的最大独立数．特别地，若图G为点传递图，则Xf(G[H]_1)=Xf(G)Xf(H)．
下面的定理3．1．4-定理3．1．7，分别证明了当图G为路，偶轮，扇，完全r部图时，Xf(G[H]_1)=Xf(G)Xf(H)=Xf(G[H])．
定理3．1．8设G，H为两个图，则Xf(G[H]_2)=Xf(H)．
下面两个结论是关于两类推广的Hajos sum构造的分数色数上下界的．
定义3．2．1给m(m≥3)个图G_0，G_1,…，G_(m-1),对i=0，1，…，m-1，令e_i=v_iv_(i+1)∈G_i，设C_m=c_0c_1…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_1(G_0,e_0，G_1，e_1，…,G_(m-1),e_(m-1))，简记为S_1．
若给定m(m≥3)个图G_i=K_(ni)，i=1，2,…，m,则S_1(G_0，e_0，G1l，e1,…，G_(m-1),e_(m-1))=S_1(K_(n1)，e_1，K_(n2)，e_2，…,K_(nm),e_m)，简记为S'_i．
定理3．2．1对上述S'_1有(?)特别地，若n_i=n,i=1，2,…，m，则Xf(S'_1)=n-1/Xf(C_m)．
定义3．2．2给n个图G_0,G_1，…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_2(G_0,e_0，G_1，e_1，…，G_(n-1),e_(n-1)，简记为S_2．
定义3．2．3对上述定义3．2．2，只将条件(3)改为(3)’连接边x_i与X_(i+3)，i=0，1，…，n-1(i+3中的加法取模n)．令此图为S'_2(G_0,e_0，G_1，e_1,…,G_(n-1),e_(n-1))，简记为S'_2．
定理3．2．2 S'_2为上述图，有(?)
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~0={u_1~0,u_2~0,…u_n~0},edge set E~0,given an integer m≥1.The m-Mycielskian of G,denoted byμ_m(G),with vertex set V(μ_m{G)) = V~0∪V~1∪V~2∪…∪V~m∪{ω}, where V~i = {v_j~i|v_j~0∈V~0} is i - th distinct copy of V~0 for i = 1,2,…, m, edge set E(μ_m(G)) = E~0∪(?)
whereμ_1(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) (b) When m is even.If XT(G)≥n+1,then XT(μ_m(G))≤XT(G)+n; If XT(G) 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~0 = {u_1~0,u_2~0,…,u_n~0},edge set E~0,given an integer m≥1. Where m - 1 copy graphs of G,denoted by G~i for i = 1,2,…,m -1,and graph G~i with vertex set V~i = {v_j~i|v_j~0∈V~0},edge set E~i={v_j~iv_j'~i|v_j~0v_j'~0∈E~0}.Another copy of V~0,denoted by V~m = {v_j~m|v_j~0∈V~0}. Similarm - Mycielskian of G,denoted byμ'_m(G) with vertex set V(μ'_m(G)) = (?){ω},edge set E(μ'_m(G))=(?)
where if m = 1,thenμ'_1(G) =μ_1(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) 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) 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_0,v_1,…,v_(2n),u_1,u_2}, edge set E(G) = {v_0v_i|i=1,2,…,2n)∪(v_iv_(i+1)|i=1,2,…,2n-1}∪{u_(2n)v_1)∪{v_1v_i|i=1,2,…,n+1)∪{u_2v_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_0,v_1…,v_n，v'_0,v'_2,…，u'_(n-1),v_0,v'_0},edge set E(G) = {v_0v_i|i=1,2,…,n}∪{v_iv_(i+1)|i=1,2,…,n-1}∪{v_nv_1}∪{u_0v_i}i=1,2,…,n}∪{v'_0v'_i|i=1,2,…,n;v'_1=v_1,v'_n=v_n}∪{v'_iv'_(i+1)|i=1,2,…,n-1;v'_1=v_1,v'_n=v_n}∪{u'_0v'_i|i=1,2,…,n;v'_1=v_1,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_1 and G_2 be vertex disjoint graphs,the Hajos sum G =(G1,x_1y_1)+(G2,x_2y_2) is obtained from G_1∪G_2 by identifying x_1 and x_2, deleting the edge x_1y_1,x_2y_2,and adding the edge y_1y_2, where x_1y_1∈E(G_1),x_2y_2∈E(G_2).
Let W_n=K_1∨C_n,V(W_n)={v_0,v_1…,v_n},E(W_n)={v_iv_(i+1)|i=1,2…,n;v_(n+1)=v_1}∪{v_0v_i|i=1,2,…,n}.W-m=K_1∨C_m,V(W_m)={v'_0,v'_1,…,v'_m},E(W_m)={v'_iv'_(i+1)|i=1,2,…,m;v'_(m+1)=v'_1}∪{v'_0v'_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_1.E'_1(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_1 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_1, m_2,△},m_1=max{r_i|i=1,2…,d(v)},m_2=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_1,u_2,…,u_m}, V(H) ={v_1,v_2,…,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]_1 with vertex set K(G[H]_1) = V(G[H]),edge set E(G[H]_1) = {(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]_1 is subgraph of G[H].Especially,if H is complete graph,thenG[H]_1=G[H].
Definition 3.1.3 Another kind of subgraph of the lexicographic product graph G[H] is denoted by G[H]_2 with vertex set V(G[H]_2) = V(G[H]),edge set E(G[H]_2)={(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_2 of length 2,then any independent set I of P_2[H]_1 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]_1)≤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]_1)=Xf(G)Xf(H).
The following Theorem 3.1.4-Theorem 3.1.7 respectively obtain Xf(G[H]_1) 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]_2)=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_0,G_1,…,G_(m-1),for i = 0,1,…, m -1,let e_i=v_iv_(i+1)∈G_i,C_m=c_0c_1…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_1 (G_0, e_0, G_1, e_1,…, G_(m-1), e_(m-1)), simply by S_1.
If given m(m≥3) graphs G_i = K_(ni) for i = 1,2,…, m,then S_1(G_0,e_0,G_1,e_1,…,G_(m-1),e_(m-1)) = S_1(K_(n1),e_1,K_(n2),e_2,…,K_(nm),e_m), simply by S'_1.
Theorem 3.2.1 For above S'_1,then (?)Especially,if n_i = n,i = 1,2,…,m,then X_f(S'_1) =n-1/Xf(C_m).
Definition 3.2.2 Given n graphs G_0,G_1,…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_2(G_0,e_0,G_1,e_1,…,G_(n-1),e_(n-1),simply by S_2.
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'_2(G_0,e_0,G_1,e_1,…,G_(n-1),e_(n-1)), simply by S'_2.
Theorem 3.2.2 If S'_2 is above graph,then max{X_f(G_i)|i = 0,1,…, n-1}-1≤X_f(S'_2)≤max{Xf(G_i)|i = 0,1,…, n - 1} + 1.
图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~0={u_1~0,u_2~0,…u_n~0},边集E~0，整数m≥1，图G的m-Mycielski图记为μ_m(G)定义为：顶点集V(μ_m(G))：V~0∪V~1∪V~2∪…∪V~m∪{ω}，其中V~i={v_j~i|v_j~0∈V~0}，i=1，2，…，m为V~0的第i个复制，边集E(μ_m(G))=E~0∪(?)．
其中μ_1(G)为图G的Mycielski图[8]．
定理2．1．1设G为n阶非空图，整数m≥1．
(a)m为奇数时．若XT(G)≥n，则XT(μ_m(G))≤XT(G)+△(G)；若XT(C)
定理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)
定义2．1．2给定图G，顶点集V~0={V_1~0，V_2~0，…，V_n~0}，边集E~0，整数m≥1．令图G的m-1个复制图记为G~i，i=1，2，…，m-1，其中G~i的顶点集记为V~i={v_j~i|v_j~0∈V~0}，边集记为E~i={v_j~iv_j~i,|v_j~0v_j~0,∈E~0)．顶点集V~0的另一个复制记为V~m={v_j~m|v_j~0∈V~0}．图G的类m-Mycielski图记为μ'_m(G)定义为：顶点集V(μ'_m(G))=(?)，边集
其中若m=1，则μ'_1(G)=μ_1(G)即为Mycielski图[8]．
定理2．1．7设G为n阶非空图，整数m≥2．若XT(G)≥n-△(G)，则XT(μ'_m(G))≤XT(C)+2△(G)；若XT(G)
定理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)
下面四个结论主要给出了推广的两类双钻图及两一般轮的Hajos sum的邻点可区别的全色数．
定义2．2．1若图G=(V,E)，其中V(G)={v_0,v_1，….v_(2n)，u_1，u_2}，E(G)=}v_0v_i|i= 1,2,…，2n)∪(viv_(i+1)+1|i=1,2,…，2n-1}∪{u_(2n)v_1)∪{v_1v_i|i=1，2，…，n+1)∪{u_2v_i|i= n+1，n+2，…，2n，1}，n≥3，则称图G为推广后的第一类双钻图．特别地，n=3为一般的双钻图[9].
定义2．2．2若图G=(V,E)；其中V(G)=(v_0,v_1…,v_n，v'_0,v'_2,…，u'_(n-1),v_0,v'_0}，(?)1,2，…,n;v'_1=v_1,v'_n=v_n}，n≥4，则称图G为推广后的第二类双钻图．特别地，n=4为一般的双钻图[9]．
定理2．2．1-定理2．2．2分别给出了这推广的两类双钻图的邻点可区别全色数．
定义2．2．3两个点不交的图G_1和G_2的Hajos sumG=(G1，x_1y_1)+(G2，x_2y_2)，是由G_1∩G_2粘合x_1,x_2为一个点，删去边x_1y_1,x_2yv2增加边y_1y_2所得，其中x_1y_1∈E(G_1)，x_2y_2∈E(G_2)．令．
定理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_1,E'_i(i=2，3，…,d(u))．其中E_i(i=2，3…，d(v))与E'_i(i=2,3…，d(u))互不相交，E_1为超星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_1,u_2,…,u_m}，V(H)={v_1,v_2,…，v_n}．它们的复合图G|H|定义为：(?)或i=k,v_jv_l∈E(H)}．
定义3．1．2复合图G[H]的一类子图，记为G[H}_1，定义为：V(G[H]_1)=V(G[H])，E(G[H]_1)={(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]_1为G[H]的子图．特别地，当H为完全图时，G[H]+1=G[H].
定义3．1．3复合图G[H]的另一类子图，记为G[H]_2，定义为：V(G[H]_2)=V(G[H])，E(G[H]_2)={(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_2，则P_2[H]_1中的任意独立集I都对应于图H的一独立集I'．
定理3．1．3设G，H为两个图，则(?)，其中α(G)为图G的最大独立数．特别地，若图G为点传递图，则Xf(G[H]_1)=Xf(G)Xf(H)．
下面的定理3．1．4-定理3．1．7，分别证明了当图G为路，偶轮，扇，完全r部图时，Xf(G[H]_1)=Xf(G)Xf(H)=Xf(G[H])．
定理3．1．8设G，H为两个图，则Xf(G[H]_2)=Xf(H)．
下面两个结论是关于两类推广的Hajos sum构造的分数色数上下界的．
定义3．2．1给m(m≥3)个图G_0，G_1,…，G_(m-1),对i=0，1，…，m-1，令e_i=v_iv_(i+1)∈G_i，设C_m=c_0c_1…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_1(G_0,e_0，G_1，e_1，…,G_(m-1),e_(m-1))，简记为S_1．
若给定m(m≥3)个图G_i=K_(ni)，i=1，2,…，m,则S_1(G_0，e_0，G1l，e1,…，G_(m-1),e_(m-1))=S_1(K_(n1)，e_1，K_(n2)，e_2，…,K_(nm),e_m)，简记为S'_i．
定理3．2．1对上述S'_1有(?)特别地，若n_i=n,i=1，2,…，m，则Xf(S'_1)=n-1/Xf(C_m)．
定义3．2．2给n个图G_0,G_1，…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_2(G_0,e_0，G_1，e_1，…，G_(n-1),e_(n-1)，简记为S_2．
定义3．2．3对上述定义3．2．2，只将条件(3)改为(3)’连接边x_i与X_(i+3)，i=0，1，…，n-1(i+3中的加法取模n)．令此图为S'_2(G_0,e_0，G_1，e_1,…,G_(n-1),e_(n-1))，简记为S'_2．
定理3．2．2 S'_2为上述图，有(?)
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~0={u_1~0,u_2~0,…u_n~0},edge set E~0,given an integer m≥1.The m-Mycielskian of G,denoted byμ_m(G),with vertex set V(μ_m{G)) = V~0∪V~1∪V~2∪…∪V~m∪{ω}, where V~i = {v_j~i|v_j~0∈V~0} is i - th distinct copy of V~0 for i = 1,2,…, m, edge set E(μ_m(G)) = E~0∪(?)
whereμ_1(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)
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~0 = {u_1~0,u_2~0,…,u_n~0},edge set E~0,given an integer m≥1. Where m - 1 copy graphs of G,denoted by G~i for i = 1,2,…,m -1,and graph G~i with vertex set V~i = {v_j~i|v_j~0∈V~0},edge set E~i={v_j~iv_j'~i|v_j~0v_j'~0∈E~0}.Another copy of V~0,denoted by V~m = {v_j~m|v_j~0∈V~0}. Similarm - Mycielskian of G,denoted byμ'_m(G) with vertex set V(μ'_m(G)) = (?){ω},edge set E(μ'_m(G))=(?)
where if m = 1,thenμ'_1(G) =μ_1(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)
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)
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_0,v_1,…,v_(2n),u_1,u_2}, edge set E(G) = {v_0v_i|i=1,2,…,2n)∪(v_iv_(i+1)|i=1,2,…,2n-1}∪{u_(2n)v_1)∪{v_1v_i|i=1,2,…,n+1)∪{u_2v_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_0,v_1…,v_n，v'_0,v'_2,…，u'_(n-1),v_0,v'_0},edge set E(G) = {v_0v_i|i=1,2,…,n}∪{v_iv_(i+1)|i=1,2,…,n-1}∪{v_nv_1}∪{u_0v_i}i=1,2,…,n}∪{v'_0v'_i|i=1,2,…,n;v'_1=v_1,v'_n=v_n}∪{v'_iv'_(i+1)|i=1,2,…,n-1;v'_1=v_1,v'_n=v_n}∪{u'_0v'_i|i=1,2,…,n;v'_1=v_1,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_1 and G_2 be vertex disjoint graphs,the Hajos sum G =(G1,x_1y_1)+(G2,x_2y_2) is obtained from G_1∪G_2 by identifying x_1 and x_2, deleting the edge x_1y_1,x_2y_2,and adding the edge y_1y_2, where x_1y_1∈E(G_1),x_2y_2∈E(G_2).
Let W_n=K_1∨C_n,V(W_n)={v_0,v_1…,v_n},E(W_n)={v_iv_(i+1)|i=1,2…,n;v_(n+1)=v_1}∪{v_0v_i|i=1,2,…,n}.W-m=K_1∨C_m,V(W_m)={v'_0,v'_1,…,v'_m},E(W_m)={v'_iv'_(i+1)|i=1,2,…,m;v'_(m+1)=v'_1}∪{v'_0v'_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_1.E'_1(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_1 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_1, m_2,△},m_1=max{r_i|i=1,2…,d(v)},m_2=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_1,u_2,…,u_m}, V(H) ={v_1,v_2,…,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]_1 with vertex set K(G[H]_1) = V(G[H]),edge set E(G[H]_1) = {(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]_1 is subgraph of G[H].Especially,if H is complete graph,thenG[H]_1=G[H].
Definition 3.1.3 Another kind of subgraph of the lexicographic product graph G[H] is denoted by G[H]_2 with vertex set V(G[H]_2) = V(G[H]),edge set E(G[H]_2)={(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_2 of length 2,then any independent set I of P_2[H]_1 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]_1)≤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]_1)=Xf(G)Xf(H).
The following Theorem 3.1.4-Theorem 3.1.7 respectively obtain Xf(G[H]_1) 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]_2)=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_0,G_1,…,G_(m-1),for i = 0,1,…, m -1,let e_i=v_iv_(i+1)∈G_i,C_m=c_0c_1…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_1 (G_0, e_0, G_1, e_1,…, G_(m-1), e_(m-1)), simply by S_1.
If given m(m≥3) graphs G_i = K_(ni) for i = 1,2,…, m,then S_1(G_0,e_0,G_1,e_1,…,G_(m-1),e_(m-1)) = S_1(K_(n1),e_1,K_(n2),e_2,…,K_(nm),e_m), simply by S'_1.
Theorem 3.2.1 For above S'_1,then (?)Especially,if n_i = n,i = 1,2,…,m,then X_f(S'_1) =n-1/Xf(C_m).
Definition 3.2.2 Given n graphs G_0,G_1,…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_2(G_0,e_0,G_1,e_1,…,G_(n-1),e_(n-1),simply by S_2.
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'_2(G_0,e_0,G_1,e_1,…,G_(n-1),e_(n-1)), simply by S'_2.
Theorem 3.2.2 If S'_2 is above graph,then max{X_f(G_i)|i = 0,1,…, n-1}-1≤X_f(S'_2)≤max{Xf(G_i)|i = 0,1,…, n - 1} + 1.
引文
[1]. J.A.Bondy.U.S.R.Murty.Graph Theory with Applications.North-Holland,1976.
[2]. Vizing,V.G..On an estimate of the chromatic class of a p- graph (Russian). Diskret. Analiz.,3(1964)25-30.
[3]. Behzad.M..Graphs and Their Chromatic Numbers.Ph.D.thesis,Michigan State University, 1965.
[4]. Zhongfu zhang etc.. On The Adjacent Vertex-Distinguish Total Coloring of Graphs.Science in China,SerA. 10(2004)574 - 583.
[5]. Weifan Wang,Kemin Zhang.Coloring of Hypergraphs.数学进展，29(2000)115- 136．
[6]. Scheinesrman E,Ullman D.Fractional graph theory,a rational approach to graph theory.New York:J.Wiley and Sons, 1997.
[7]. Peter Che Bor Lam,Lin Wensong.Gu Guohua, Song Zengmin.Circular chromatic number and a generalization of the construction of Mycielski. Journal of Combinatorial Theory,Series B,89(2003)195 - 205.
[8]. Mycielski,J..Sur Le coloring des graphes.Colloq.Math.,3(1955)161-162.
[9]. M.Voigt.On list colorings and choosability of graphs.Technische univeritatilmenau,D-98684 ilmenau, 1998.
[10]. Bela Bollobas.Modern Graph Theory.Springer-Verlag New York,Inc.l998.
[11]. Zhongfu Zhang,Linzhong Liu.Jianfang Wang.Adjacent strong edge coloring ofgraphs. Applied Math.Letters,15(2002)623-626.
[12]. Sandi Klavzar.Coloring graph products-A survey.Discrete Mathematics, 155(1996)135- 145.
[13]. X.Zhu.An analogue of Hajds theorem for the circular chromatic number.Proceedings of the American Mathematical Society,129(2001)2845 - 2852.
[14]．李慰萱．图论．中国：湖南科学技术出版社， 1980．
[15]. H.P.Yap and K.H.Chew.Total chromatic number of graphs of high degreⅡ.J.Aus- tralian Math.Soc.,Ser.A,53(1992)219-228.
[16]. A.J.W.Hiltion and H.R.Hind.Total chromatic number of graphs having largmaximum degree. Discrete Math.,117(1993)127-140.
[17]. O.V.Borodin.A.V.Kostochka and D.R.Woodall.List edge and list total colorings of multigraphs.J.Combinatorial Theory.Series B,71(1997),184-204.
[18]. A.V.Kostochka.The total chromatic number of any multigraph with maximundegree five is at most seven.Discrete Math.,162(1996)199-214.
[19]. Daniel Kral,Jan Kratochvil,Andrzej Proskurowski.Coloring mixed hypeetreesDiscrete Applied Mathematics,154(2005)660 - 672.
[20]. Patric R.J. Ostergard.On a hypercube coloring problem. Journal of Combinatorial Theory, Series A,108(2004)199 - 204.
[21]. Voloshin V.The mixed hypergraphs.Computer Science J.Moldova,1(1993)45-52.
[22]．龚劬，杨鹏辉．星的全着色和计数．重庆大学学报(自然科学版)，(5)30(2007)
[23].王顺年，山东师范大学硕士学位论文， 2007年4月．
[24]. X.Zhu.Uniquely H-colorable graphs with large girth.J.Graph theory,23(199633-41.
[25]. Kilakos.K. and B.Reed.Fractionally coloring total graphs.Combinatorica,1(?) (1993)435-440.
[26]．韩淑芹，山东师范大学硕士学位论文， 2007年4月．
[27]. Dietel Reinhard.Graph Theory.Springer Verlag New York,Inc.1997.
[28]. Chartrand G.,Lesniak-Foster L..Graph and Digraphs.Ind.Edition,WadswortlBr- ooks/Cole,Monterey,CA,1986.
[29]. Hansen P.,Marcotte O.,Graph coloring and application.AMS providence,RhodIsland USA, 1999.
[30]. Behzad.Graphs and their chromatic numbers.Doctoral Thesis,Michigan StatUniversity, 1965.
[31]. Behzad.M..The total chromatic number of a graph:a survey.in Com-binatoriaMathematics and its Applications,Academic Press(1971)1-8.
[32]. Yap H.P..Total coloring of graphs.Lecture Notes in Mathematics.1623(1996) 1-131.
[33]. M.Behzad,G.Chartrand and J.K.Cooper Jr..The color numbers of complete graphs. J.London Math.Soc.,42(1967)226-228.
[34]. J.C.Bermond.Nombre chromatique total du graph r-parti complet.J.London Math. Soc., (2)9(1974)279-285.
[35]. P.N.Balister,B.Bollobas,R.H.Shelp.Vertex distinguishing colorings of graphs with △(G) = 2.Discrete Math.,252(2002)17-29.
[36]. C.Bazgan,A.Harkat-Benhamdine,Hao Li.M.Wozniak.On the vertex-distinguishing proper edge-coloring of graphs. J.Combin.Theory Ser.B,75(1999)288-301.
[37]. A.C.Burris and R.H.Schelp. Vertex-distinguishing proper edge-colorings.J of Graph Theory, 26(1997)73-82.
[38]．孙艳丽，山东师范大学硕士学位论文， 2006年4月．
[39]．卜月华，张克民.超图-有限集合的组合学．南京：东南大学出版社，(2002)2- 90．
[40]. Lovasz,L.,Kneser's conjecture.Chromatic number,and homotopy.J.Comb.Theory(Ser.A)25(1978)319-324.
[41]. Stahl,S..n-tuple colorings and associated graphs. J.Comb.Theory(Ser.B)20(1976)185-203.
[42]. S.Klavazar.A note on the fractional chromatic number and the lexicographicproduct of graphs.preprint, 1996.
[43]. D.C.Fisher.Fractional colorings with large denominators.J.Graph Theory,20(1995)403-409.
[44]. X.Zhu.An analogue of Hajos theorem for the circular chromatic number(Ⅱ) .Graphs and combinatorics,19(2003)419 - 432.
[45]. M.Larsen,J.Propp and D.Ullman.The fractional chromatic number of Mycielski'sgraphs. J.Graph Theory,19(1995)411-416.
[46]. Claude Tardif.Fractional Chromatic Number of Cones Over Graphs.Graphtheory, 38(2001)87 - 94.
[47]. Lin Wensong.Peter Che Bor Lam etc..Circular chromatic numbers of the gen- eralized Mvcielskians of cycles. Joural of nanjing university mathematical biquarterly, (2)23(2006)232 - 241.
[48]. N.Cizek and S.Klavzar.On the chromatic number of the lexicographic product and the Cartesian sum of graphs.Discrete Math.,134(1994)17～24.
[2]. Vizing,V.G..On an estimate of the chromatic class of a p- graph (Russian). Diskret. Analiz.,3(1964)25-30.
[3]. Behzad.M..Graphs and Their Chromatic Numbers.Ph.D.thesis,Michigan State University, 1965.
[4]. Zhongfu zhang etc.. On The Adjacent Vertex-Distinguish Total Coloring of Graphs.Science in China,SerA. 10(2004)574 - 583.
[5]. Weifan Wang,Kemin Zhang.Coloring of Hypergraphs.数学进展，29(2000)115- 136．
[6]. Scheinesrman E,Ullman D.Fractional graph theory,a rational approach to graph theory.New York:J.Wiley and Sons, 1997.
[7]. Peter Che Bor Lam,Lin Wensong.Gu Guohua, Song Zengmin.Circular chromatic number and a generalization of the construction of Mycielski. Journal of Combinatorial Theory,Series B,89(2003)195 - 205.
[8]. Mycielski,J..Sur Le coloring des graphes.Colloq.Math.,3(1955)161-162.
[9]. M.Voigt.On list colorings and choosability of graphs.Technische univeritatilmenau,D-98684 ilmenau, 1998.
[10]. Bela Bollobas.Modern Graph Theory.Springer-Verlag New York,Inc.l998.
[11]. Zhongfu Zhang,Linzhong Liu.Jianfang Wang.Adjacent strong edge coloring ofgraphs. Applied Math.Letters,15(2002)623-626.
[12]. Sandi Klavzar.Coloring graph products-A survey.Discrete Mathematics, 155(1996)135- 145.
[13]. X.Zhu.An analogue of Hajds theorem for the circular chromatic number.Proceedings of the American Mathematical Society,129(2001)2845 - 2852.
[14]．李慰萱．图论．中国：湖南科学技术出版社， 1980．
[15]. H.P.Yap and K.H.Chew.Total chromatic number of graphs of high degreⅡ.J.Aus- tralian Math.Soc.,Ser.A,53(1992)219-228.
[16]. A.J.W.Hiltion and H.R.Hind.Total chromatic number of graphs having largmaximum degree. Discrete Math.,117(1993)127-140.
[17]. O.V.Borodin.A.V.Kostochka and D.R.Woodall.List edge and list total colorings of multigraphs.J.Combinatorial Theory.Series B,71(1997),184-204.
[18]. A.V.Kostochka.The total chromatic number of any multigraph with maximundegree five is at most seven.Discrete Math.,162(1996)199-214.
[19]. Daniel Kral,Jan Kratochvil,Andrzej Proskurowski.Coloring mixed hypeetreesDiscrete Applied Mathematics,154(2005)660 - 672.
[20]. Patric R.J. Ostergard.On a hypercube coloring problem. Journal of Combinatorial Theory, Series A,108(2004)199 - 204.
[21]. Voloshin V.The mixed hypergraphs.Computer Science J.Moldova,1(1993)45-52.
[22]．龚劬，杨鹏辉．星的全着色和计数．重庆大学学报(自然科学版)，(5)30(2007)
[23].王顺年，山东师范大学硕士学位论文， 2007年4月．
[24]. X.Zhu.Uniquely H-colorable graphs with large girth.J.Graph theory,23(199633-41.
[25]. Kilakos.K. and B.Reed.Fractionally coloring total graphs.Combinatorica,1(?) (1993)435-440.
[26]．韩淑芹，山东师范大学硕士学位论文， 2007年4月．
[27]. Dietel Reinhard.Graph Theory.Springer Verlag New York,Inc.1997.
[28]. Chartrand G.,Lesniak-Foster L..Graph and Digraphs.Ind.Edition,WadswortlBr- ooks/Cole,Monterey,CA,1986.
[29]. Hansen P.,Marcotte O.,Graph coloring and application.AMS providence,RhodIsland USA, 1999.
[30]. Behzad.Graphs and their chromatic numbers.Doctoral Thesis,Michigan StatUniversity, 1965.
[31]. Behzad.M..The total chromatic number of a graph:a survey.in Com-binatoriaMathematics and its Applications,Academic Press(1971)1-8.
[32]. Yap H.P..Total coloring of graphs.Lecture Notes in Mathematics.1623(1996) 1-131.
[33]. M.Behzad,G.Chartrand and J.K.Cooper Jr..The color numbers of complete graphs. J.London Math.Soc.,42(1967)226-228.
[34]. J.C.Bermond.Nombre chromatique total du graph r-parti complet.J.London Math. Soc., (2)9(1974)279-285.
[35]. P.N.Balister,B.Bollobas,R.H.Shelp.Vertex distinguishing colorings of graphs with △(G) = 2.Discrete Math.,252(2002)17-29.
[36]. C.Bazgan,A.Harkat-Benhamdine,Hao Li.M.Wozniak.On the vertex-distinguishing proper edge-coloring of graphs. J.Combin.Theory Ser.B,75(1999)288-301.
[37]. A.C.Burris and R.H.Schelp. Vertex-distinguishing proper edge-colorings.J of Graph Theory, 26(1997)73-82.
[38]．孙艳丽，山东师范大学硕士学位论文， 2006年4月．
[39]．卜月华，张克民.超图-有限集合的组合学．南京：东南大学出版社，(2002)2- 90．
[40]. Lovasz,L.,Kneser's conjecture.Chromatic number,and homotopy.J.Comb.Theory(Ser.A)25(1978)319-324.
[41]. Stahl,S..n-tuple colorings and associated graphs. J.Comb.Theory(Ser.B)20(1976)185-203.
[42]. S.Klavazar.A note on the fractional chromatic number and the lexicographicproduct of graphs.preprint, 1996.
[43]. D.C.Fisher.Fractional colorings with large denominators.J.Graph Theory,20(1995)403-409.
[44]. X.Zhu.An analogue of Hajos theorem for the circular chromatic number(Ⅱ) .Graphs and combinatorics,19(2003)419 - 432.
[45]. M.Larsen,J.Propp and D.Ullman.The fractional chromatic number of Mycielski'sgraphs. J.Graph Theory,19(1995)411-416.
[46]. Claude Tardif.Fractional Chromatic Number of Cones Over Graphs.Graphtheory, 38(2001)87 - 94.
[47]. Lin Wensong.Peter Che Bor Lam etc..Circular chromatic numbers of the gen- eralized Mvcielskians of cycles. Joural of nanjing university mathematical biquarterly, (2)23(2006)232 - 241.
[48]. N.Cizek and S.Klavzar.On the chromatic number of the lexicographic product and the Cartesian sum of graphs.Discrete Math.,134(1994)17～24.