(Adjacent) Vertex-distinguishing Total Colorings And Fractional Colorings Of Graphs

In this article , we use [x] for the maximum integer which is no more than the real number x , we use [x] for the minimum integer which is no less than the real number x . We denote by |S| the number of the elements in the set .All graphs considered are simple , finite and undirected . For a graph G , we denote the vertex set and the edge set of G by V(G) and E(G) , respectively. We use dc(v) for the degree of v in V(G) and A(G) for the maximum degree of G and δ(G) for the minimum degree of G . Let G[V'] denote the induced subgraph of G with vertex set V' and G[E'] denote the induced subgraph of G with edge set E'. We denote by K_n the complete graph on n vertices . We use the symbols ω(G) and κ(G) to denote the number of components of G and the connectivity of G . The independence number of G is denoted by α(G) and the chromatic number of G is denoted by x(G) . For any undefined notation and terminology , we refer the reader to [1] .The definition of (adjacent) vertex-distinguishing total coloring by Zhang Zhongfu is as follows : Let G(V, E) is a simple and connected graph of which the order is at least 2 , k is an positive integer and f is the mapping from V(G)∪E(G) to C ={1,2,...,k}.For any vertex u 6 V(G) , denote C(u) = {f(u)}∪{f(uv)|uv ∈ E(G)} , C(u) = C- G(u) .(1) For any edge uv ,vw ∈ E(G) , and u ≠w , there is f(uv) ≠ f(vw) .(2) For any edge uv 6 E(G) , and u/t), there is f(u) ^ f(v) , f(u) ^ f(uv), f(uv) ^ f(v) .(3) For any edge uv e E(G) , and u / v , there is C(u) ^ C(v) .(4) For any vertex u,v €. V(G) , and ?/?, there is C(it) 7^ C(v).If (1) , (2) are satisfied , then / is called a A;-total coloring of graph G(in brief, it is noted as k-TC) .If (1) , (2) , (3) are satisfied , then / is called a A;-adjacent vertex-distinguishing total coloring of graph G (in brief , it is noted as k-AVDTC) .If (1) , (2) , (4) are satisfied , then / is called a k- vertex-distinguishing total coloring of graph G (in brief , it is noted as k-VDTC) .The total chromatic number of G isXt(G) = min{A;| G has k-TC}.The adjacent vertex-distinguishing total chromatic number of G is Xat{G) = min{k\ G has k-AVDTC}.The vertex-distinguishing total chromatic number of G is Xvt{G) = min{A;| G has k-VDTC}.The following results about adjacent vertex-distinguishing total coloring are right , apparently .For a simple connected graph G of order n (n = \V{G)\ > 2) , adjacent vertex-distinguishing total chromatic number Xat{G) exist , andXat(G) > A(G) + 1.If G(V, E) has two adjacent maximum degree vertices , thenXat(G) > A(G) + 2.The following conjecture is proposed by Zhang Zongfu in [4]:For a simple connected graph G of order n (n — \V{G)\ > 2) , thenXat(G) 2) , thenKT(G) = max{t\t = min{^|(C^+1) > nd},5(G) < d < A(G)} . Let nd — nd{G) denote the number of all vertices of degree d in a graph G .The definition of fractional coloring is given in [6] by E.Scheinerman and D.Ullman, it is fractional generalization of coloring of graphs . Obtain every graph's fractional chromatic number is iVP-hard .A mapping C from the collection C of independent sets of a graph G to the interval [0, 1] is a fractional-coloring if for every vertex x of G , we have Tlie<;,s.t.xGi C{I) > 1 ? The value of a fractional-coloring C is E/€c,5.t.ze/C(-0-The fractional chromatic number Xf(G) °f G ls the infimum of the values of fractional-coloring of G .Frational-coloring of a graph G has an equivalent definition . Xf{G) =\\m **L1 - inf 2^LJ. , Xb{G) is the 6-fold chromatic number of G . Assigns6—>oo b b bto each vetex of G a set of b colors , and adjacent vertices receive disjoint sets of colors , if all colors are draw from a palette of a colors , We say that G is a : 6-colorable . We sometimes refer to such a coloring as an a : 6-coloring . The least a for whiqh G has a : 6-coloring is the 6-fold chromatic number of G .Xb(G) — min{ a \ G has a : 6-coloring}.In this paper , about (adjacent) vertex-distinguishing total coloring of graphs, we have the following theorems .The graph with vetex set V(G) — {u;[} Vj\i = 1, 2, â–  â–  ?, m;j = 1, 2, â–  ? ?, n;m > n > 2} and edge set E(G) = {v,iVj\i = 1, â–  ? ?, m;1 < j < i} , We called "hypo-complete graph " . Denote by : G*mn .Theorem 2.1.1 Xat(G*m>n) = { ^[m + l,m> n>2.Add edge ViVn (i = 1, ? ? ?, n) to ^ of Cn — vxvi â–  â–  â–  vnv\ , denote by Add edge vxva (i = 1, ? ? ?, n) to Vi of Y^ , denote by Y^;? â–  ?;Add edge (i = 1, â–  â–  â– , n) to Vi of y^"1) â–  ? ? , denote by Y^ .... yji) is Qn .Theorem 2.1.2 XaMk)) = k + A (n > 3) . Theorem 2.1.3 x,t(>;(1)) = Xvt(Qn) = n (n > 5) .Add edges UjUj , UiVi+l , ??? , UjUj+fc , ??^,iiiui+(n₁) , (i = 1,2, ??â– ,n;/c = 0,1, ? ? ?, n — 1;where i + k > n + l , i + k with addition modulo n ) to both C\ = U1U2 ? ? -unui(n > 3) and C2 = ^1^2 ? â–  â– ^n^i(" > 3) , denote these graphsTheorem 2.1.4 Where n > 4 and n = 0{mod2) ,Theorem 2.1.5 Where n > 4 and n = I(raod2) , (1) XatiCU) = 5, . ..(2)Where 1 ) < k + 6 .Add edges UiV^i and UiVi+i (i = 2,3, ? ? ?, n — 1) to Ui of <5n(" > 3);Add edges u\V2 and uaun to iti;Add edges uni>n_i and ???! to un , denote this graph by Q*n .Theorem 2.1.6 Xat{Q*n) = 7 (n > 3) .Doubble edge ViVi+i( where % — n ,it is vnv{) of Cn = vxv2 ? â–  â–  vnv\(n > 3) , add vetex u^ (i — 1,2, ? ? ?, n) in outside edge , denote this graph by Hn .Theorem 2.1.7 Xat{Hn) = 6 (n > 3)Add vetex ty, (i = 1,2, ? ? â– , n) in edge V{Vi+i ( where i = n , it is vnv\) of i/n(n > 3) , denote this graph by P* .Theorem 2.1.8 Xt{P$ = Xat(P*n) = 5 (n > 3) .Add edges WjiXj (z = 1,2, â–  ? ?, 2n) to each vertex Vi of Cin = (n > 2) , also add edges UjUj+i (i = I(mod2)) ,/denote this graph byTheorem 2.1.9 xat(W^) = 5 (n > 2) .In this paper , about fractional coloring of graphs , we have the following theorems .Let o and b be positive integers with a > 26 . Let Ga,b be the graph'6];with vertex set.V{Ga,b)={ v0 , vx , â–  â–  â–  , ua_i };The neighbors of vertex v{ are { vi+b, vi+b+i , ? ? ? , vi+a+b } with addition modulo a .Graph G is called vertex-transitive '6': for every pair of vertices u , v €V(G) there exists an automorphism of G with tt(u)=v .Proposition 2.2.1? xf(Ga,b) = f;Xb(Ga,b) = a .Proposition 2.2.2^ For any graph G , Xf(G) > ^ . Furthmore, if G is vertex-transitive , then equality hold .Lemma 2.2.3 For any vertex v e V{Ga>b) , ^ < Xf(Ga,b - v) < f .Theorem 2.2.4 Where a = kb , k e Z and k > 2 , there is Xf(GaJ, - v) = f .Theorem 2.2.5 Where a = 26 + 1 , there is Xf(Ga,b - v) = ^ .In Gajb graph ,let e^ = (i>j, Vi+b) , z = 0,1, ? ? ?, a — 1 . i + 6 with addition modulo a .Theorem 2.2.6 Where e^e{ , there is Xf(Ga,b - e) = f . Lemma 2.2.7 s=± < Xf(Ga,b - e{) < f , i = 0,1, â–  ? ?, a - 1 .Theorem 2.2.8 Where a = kb , k e Z and A;> 2 , there is X/(Ga,b - ei) = f , i = 0,1, ? ? ?, a - 1 .Theorem 2.2.9 Where a = 26 + 1 , there is Xf(Ga,b - e{) = ^, i = 0,1, ? ? â– , a — 1 .Theorem 2.2.10 Where a - kb , k e Z and A;> 2 , there is Xf(Ga,b U (t>j, Uj)) = | for arbitrary nonadjacent vertices V{ , Vj in.Gaij, .Theorem 2.2.11 x/(Ga,hu(^ , vi+1)) > xf{Gajb) , i = 0,---,a- 1...