The Total Coloring, The Adjacent Vertex-distinguish Total Coloring And The Fractional Coloring Of Graphs

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)m(G))≤n+â–³(G)(b) When m is even.If XT(G)≥n+1,then XT(μ_m(G))≤XT(G)+n; If XT(G) 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)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)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.