【作者】 孙艳丽；

【导师】 孙磊；

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

【摘要】 染色问题及许多图理论都是源自四色问题的研究。另外染色问题在组合分析和实际生活中有着广泛的应用,是图论研究中一个很活跃的课题,各类染色问题被相继提出并加以发展、应用。 图G的一个(正常)k-染色是将k种染色分配给G的顶点集V(G),使得相邻两顶点的颜色不同。定义色数为:χ(G)=min{k|图G有k-染色}。类似的,图G的一个(正常)k-边染色是将k种染色分配给G的边集E(G),使得有公共端点的两边的颜色不同。边色数χ′(G)=min{k|图G有k-边染色}。 全染色的概念是对点染色和边染色的推广,图的所有元素(顶点和边)都将染色且任相邻或关联的元素染色不同。全染色是图论染色的一个传统问题,由Vizing(1964)[23]和Behzad(1965)[24,25]各自独立提出的,同时分别给出全染色猜想。点可区别全染色和邻点可区别全染色[2]是染色问题的新生点,近来由张忠辅提出并给出了相应的两个猜想。 定义 设G(V,E)为图,k为正整数,S为k-色集,令映射f:V(G)∪E(G)→S。如果 (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-全染色。若还满足 (3)对任意u,v∈V(G),C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}那么称f为图G的一个点可区别的k-全染色(简记为k-VDTC)。 若条件(3)改为更多还原

【Abstract】 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 + A(G).Corollary 2.1.2 Suppose G is a graph with n vertices.If A(G) = n — 1 and xt{G) = A(G) + 1 ,then xt{M{G)) = A(M(G)) + 1 .Theorem 2.1.3 Suppose G is a graph with n vertices .If Xvt(G) > n,thenXvt(M{G)) < Xvt(G) + A(G);if Xvt(G) < n,then Xvt{M(G)) <n + A(G).Theorem 2.1.4 Suppose G is a graph with n vertices and 5(G) > 2, and A;is a positive integers.If Xvt(G) < A(G) + k and A(6*) + k > n ,then Xvt(M(G))<A(M(G)) + k.Corollary 2.1.5 Suppose G is a graph with n vertices and & is a positive integers.If Xat{G) < A(G) + k and A(G) + A;> 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) <Lemma 3.3.1 Suppose G is a graph,if x" (G) — A(G) 4- l,then x"f(G) —Theorem 3.3.2 Suppose Cn is a cycle with n vertices,and k is a positive integer,thenx"f(cn) =3 + \ n = 3fc + 1\Theorem 3.3.3[12] For complete graph Kn,n n is odd numbern + 1 n is even numberTheorem 3.3.4^ For complete bipartite graph? ? fmax{m,n} + l m^nXf{Km,n) = X {Km,n) = <[ n + 2 m — nTheorem 3.3.5l13]Xf(K(rin))=x"(K(r,n)) =A(K(r, n)) + 2 r = 2 or r is even numberA(Ar(r,n))and n is odd number other更多还原