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

The coloring problem and some other graph theories are all from the study of the celebrated four color problem.In the combinatorial mathematics and our living ,the coloring problem has a big application,and 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 (verteics and edges) of the graph are colored in such a way that no two adjacent or incident elements are colored the same.It's a traditional coloring problem and was introduced by Vizing(1964) and independently Behzad(1965) with total coloring conjecture[23,24,25].The vertex-distinguishing total coloring and the adjacent vertex-distinguishing total coloring are two new coloring problem and were presented by Zhongfu Zhang with two conjecture resentely[2].Definition Suppose G(V(G),E(G)) is a graph,A;is a positive integer and S is a fc-element set.Let / be a map from V(G) U E(G) to S.Ifl).for any uv,vw e E(G),u ^ w,there is f(uv) ^ f(vw)2).for any uv e ￡(G),there are /(u) ^ f(v),f(u) + f(uv)J{uv) # /(?) then / is called a &-total coloring of graph G and the total-chromatic number is defined as xt(G)(ov denoted as x"{G)) = min{/c|graph G has fc-total-colorings}.If / also satisfies3).for any u,v € V(G),there is C{u) ^ C(^);where C{u) = {f(u)} U {f(uv)\uv € E(G)} is called the color set of vertex u .then / is called a vertex-distinguishing /c-total coloring of graph G(briefly noted as A-VDTC) and Xvt(G) = minj^lC has k-VDTC} is called vertex-distinguishing total chromatic number of graph G.If condition 3) is changed to3') .for any uv G E(G),there is C(u) + C{v)then / is called a adjacent vertex-distinguishing ft-total coloring of graph (?(in brief,noted as &-AVDTC) and Xat{G) = min{k\G has A;-AVDTC} is called the adjacent vertex-distinguishing total chromatic number of graph G.Total Coloring Conjecture For any simple graph G,xt{G) < A(Gf) + 2.Adjacent Vertex-Distinguishing Total Coloring Conjecture Forany simple graph G,xat(G) < A(G) + 3.Vertex-Distinguishing Total Coloring Conjecture For any simplegraph G,kT{G) < Xvt(G) < kT(G) + l.where kT(G) = min{/|Cf+1 > nd,6 < d < A, rid is the number of the vertices with degree d in graph G}.The problem of determining the total chromatic number of a graph is NP-hard,and we obtain some resultes for a lot of graph classes and graphs with certain conditions in this field.So far,the studies of the vertex-distinguishing total coloring and the adjacent vertex-distinguishing total coloring are for thespecial graphs.At present,there were few results about fractional coloring of graph.Some results are about the fractional chromatic numbers and m-fold chromatic numbers of some special graphs,the other are about whether some conjecture in coloring problem were true in fractional case.The total coloring conjecture has been proved true in the fractional coloring[ll].In this thesis.the first part deals with the relations between the basic graphs and their Mycielski graphs or the Cartesian product graphs on the total coloring and the (adjacent)vertex- distinguish total coloring,and we obtain some sufficient conditions with which the constructional graphs satisfy the total coloring conjectrue and the adjacent total coloring conjectrue. The second part focuses on the m-bold coloring of the Kneser graphs and a cir-culant graph Gait, firstly.The m-bold coloring number of Ga^ graph has been determined completely but the Kneser graphs haven't .Secondly it studies the fractional coloring of the Cartesian product graphs and the fractional total chromatic number of some special graphs(for exampleicycle,complete graph,complete bipartite graph, balanced complete r-partite graph).We briefly summerize our main results as follow:We call the graph obtained by the Mycielski Constructional] the Mycielski graph.Given a graph G with V{G) = {v\,v2, ? ■ ■ ,■?;?},the Mycieski graph(denoted by M{G)) of G is denned to be a graph with V(M{G)) = Vu{v[,v'2,---X,u} and E(M(G)) = E(G) U {v^v^ e E(G),i,j = I,--- ,n}U{v'iuj\i = 1, ???,7i}.Theorem 2.1.1 Suppose G is a graph with n vertices.If Xt(G) > n,then Xt(M(G)) < Xt(G) 4- A(G);if Xt(G) < n,then Xt(M{G)) n,thenXvt(M{G)) < Xvt(G) + A(G);if Xvt(G) < n,then Xvt{M(G)) 2, and A;is a positive integers.If Xvt(G) < A(G) + k and A(6*) + k > n ,then Xvt(M(G)) n,then Xat(M(G)) < A{M{G))+k.Corollary 2.1.6 Suppose graph G satisfies the conditions of Corollary 2.1.4.If the adjacent vertex-distinguishing total coloring conjecture is true for G,then M(G) satisfies the conjecture too.Furthermore,if k = 1 then the above two results can be written to Xvt(M(G)) — A(M(G)) + 1 and Xat(M(G))=A(M(G)) + l.The following four results are about the adjacent vertex-distinguishing total coloring of the Cartesian product graphs.For graphs G\ = (Vi, E\) and G2 — (V^^jthe Cartesian product graph G\ x Gi has vertex set V\ x V2 and in which (i/1;u\) is adjacent to (w2, u2) if and only if either V\Vi 6 E\ and ui =u2 e V2 or vi — v2 ￡ Vi and uxu2 ￡ E2.Theorem 2.2.2 Suppose G, H are two graphs,and k > 1 is a positive integer. If A(G)+2 < Xat(G) < A(G)+k,X'(H) = A(H) and X(H) < A(G)+k, then Xat{G x H) < A(G x H) + k.Theorem 2.2.3 If the adjacent vertex-distinguishing total coloring conjecture is true for graph G,x'(H) = A(H) and xiH) < Xat(G),then G x H satisfies the conjecture too.Theorem 2.2.4 Suppose G, H are two graphs,and k > 1 is a positive integer. If A(G) + 2 < Xat(G) < A(G) + k and x(H) < A(G) + k, thenxH)< A(GCorollary 2.2.5 Suppose G, H are two graphs,and k > 1 is a positive integer. If Xat{G) < A(G) + 2 and x(if) < A(G),then G x if satisfies the adjacent vertex-distinguishing total coloring conjecture.Suppose Pn = u\Ui ■ ? ■ un andPn = V\V2 ■ ? ? vn are two paths.Let's overlay matchings UiVi, UjUj+i, ? ? ?, utvi+k, ? ? ■, Ujt>j+(n_i) between the two paths successively (i — 1, 2. ? ? ?, n, k — 0,1, ? ? ? ,n — l.get mod n when z +ft > n"+ l).So we can obtain a sequence of graphs:P^], PQ, ■■■, P^+l\ ??-, P}$ = Pn V Pn.Suppose Vi = {ui,u2,---,un},V2 = {vx,v2,-■ ■ ,vn},uxu2-■-UnUi and Viv% ? ? ? un7;i are two cycles.Similarly,we overlay the above matchings between the bipartition (Vi, V2) successively. A sequence of regular bipartite graphs:G^]j, G^n, ? ? ?, G^1^, ? ? ?, G^n — Knyn can be obtained.we can obtain a sequence of regular graphs C$, Cg>, ? ? ?, Cf+1), ? ■ ?, Cg = Cn V Cn by overlaying the above matchings between the two cycles.Theorem 2.3.1 XatiP^) = A(^fcn+1)) + 2 - k + 5(k = 0,1, ? ■ ?, n -Theorem 2.3.2 Xat{G^) = A(G^1)) + 2 = A: + 3(fc = 0,1, ? ? ■, n -l,n > 3).Corollary 2.3.3 Xt(P￡+1)) < A(P￡+1)) + 2,Xr(G'gn+1)) < ( 2,that is to say P^1^ and G^1' satisfy the total coloring conjectrue.Theorem 2.3.4 Xt{C^) < A(C^) + 2 = k + 5(/fc = 0,1, ? ? ■, n -l,n> 3).Theorem 2.3.5 Xat{Cn,n) = 5 (n > 3)Theorem 2.3.6 Xat(W2n) = \ 6 n 3'4( n + 1 n > 5Corollary 2.3.7 The total coloring conjecture is true for W2n, and whenTheorem 2.3.8 Let G be a graph with edge-connectivity X(G) = 1 , suppose uoVq be any cutedge ,Gi,G2 be connected components of graph G - uQv0 and u0 e V(Gi), v0 € V(G2).ThenA(G) 4- 2 d(uo) — d(v0) = A(G),Xat(Gi U uovo)= Xat(G2Uu0v0) = A(G) + 1 ma.x{xat(Gi UuoVo),Xat(G2 U wo^o)} otherwiseIn following we will introduce two important graphs:Kneser graphs and Gafi graph.Suppose a > 26, a, b are two positive integers.The Kneser graph Ka:b has vertices all the b- subsets of a a-set,and two vertices are adjacent if and only if the two subsets are disjoint. The graph Ga](,[29] which is special circulant graph has vertices 0,1, ? ? ■ ,a — l,and the vertices i.j are adjacent if and only if b < \i — j\ < a — b. Kneser graphs and Ga^ graph respectively play important roles in the fractional coloring and the circular coloring,what complete graphs play in the ordinary coloring.Stahl[17] proposed the conjectrue:for any positive integer m, Xm(Ka:b) = a — 2b + 2m is true. [14] has been proved the conjectrue is true for 1 < m < b,and the following theory will prove the conjectrue is wrong for m > b.Theorem 3.1.1 When a>2b,m> b,xm(Ka:b) ^a-2b + 2m. Theorem 3.1.2 Xmb{Ka:b) — ^a (a,b,m are positive integers). Theorem 3.1.4 Suppose a,b,m are positive integers,Lemma 3.2.1 Suppose G, H are two graphs,x(GxH) = max{x{G), x(H)}.Theorem 3.2.2 Suppose G, H are two graphs,if Xf(G) = x{G) and X(H) < X(G),then Xf(G x H) =Theorem 3.2.3 Suppose graph G has a Hamilton cycle,and H is bipartite graph,then Xf(G x H) = Xf{G)-Theorem 3.2.4 Suppose a, b are positive integers and a > 26,if x{H)