| The vertex coloring is the focus of research in the graph theory. A k — coloring of a graph G is a mapping f from V(G) to {1,2, ..., k). With respect to a given k-coloring, Vi denotes the set of all vertices of G colored with i, and G[Vi] denotes the subgraph induced by Vi in G. If Vi is an independent set for every 1 ≤ i≤ k, then f is called a. proper k—coloring. The chromatic number x(G) of a graph G is the minimum number k of colors for which G has a proper k—coloring. If x(G) =k, then G is said to be k — chromatic. We say that a graph G is critical if x(H) < x(G) for every proper subgraph H of G. A k—critical graph is one that is k—chromatic and critical; every k—chromatic graph has a k—critical subgraph.If Vi induces a subgraph whose connected components are trees, then f is called a tree k — coloring. The vertex arboricity of a graph G, denoted by va{G), is the minimum number k for which G has a tree k—coloring.Kronk et al proved that va(G) ≤ [(△(G)+1)/2] for any graph G. Catlin et al proved that for neither a cycle nor a clique G, va(G) ≤ [△(G)/2]. Skrekovski proved that locally planar graphs have vertex arboricity < 3 and that triangle-free locally planar graphs have vertex arboricity ≤ 2. Chartrand et al also proved the vertex arboricity of a planer graph ≤ 3 and va(K(p1,p2,... ,pn)) = n - max{k| ∑0kpi≤n-k} for the complete n-partite graph K(p1,p2,... ,pn), where p0 = 0 and 1 ≤ p1 ≤ p2 ≤ ... < pn. Latter, many people, for example, N.Alon et al, studied the vertex arboricity of graphs, too.If Vi induces a subgraph whose connected components are paths, then f is called a path k-coloring. The vertex linear arboricity of a graph G, denoted by vla(G), is the minimum number k for which G has a path k-coloring. Clearly, for any graph G, va(G) ≤ vla(G) ≤ x(G).Matsumoto proved that for a finite graph G, vla(G) ≤ [(△(G)+1)/2 ], moreover, if A(G) is even, then vla(G) =[ (△(G)+1)/2] if and only if G is a complete graph of orderA(G) + 1 or a cycle. Goddard and Poh proved that vla{G) < 3 for a planar graph G. Akiyama etal proved vla(G) < 2 if G is an outerplanar graph. Alavi etal proved vla(G) + vla(G) < 1 + l"2^! f°r anY graph G of order n where G is the complement ofG.Given any set D of positive real numbers, let G(R, D) denote the graph whose vertices are all the points of the real line R, such that any two points x, y are adjacent if and only if |x — y\ € D. This graph is called a distance graph and the set D is called the distance set of the graph. If D is a set of positive integers, then the subgraph of G(R,D) induced by the set Z of all integers, denoted by G(D), is called an integer distance graph.Coloring problems on distance graphs are motivated by the famous Hadwiger-Nelson unit distance plane coloring problem which asks for the the minimum number of colors necessary to color the points of the Euclidean plane (i.e., V(G) = R2) such that pairs of points of unit distance (i.e., D = {1}) are colored differently. The result 4 < x(G(R2, {1})) < 7 was obtained. No substantial progress has been made on the problem till now. Integer distance graphs were introduced by Eggleton etal and the real distance graph was studied by them in 1985.More results on the chromatic number of special integer distance graphs were obtained by G.J.Chang. Eggleton, Erdds, Skilton, Kemnitz, Kolberg, Marangio, Voit, Walther, Kronk and Wall et at let Dm,k,s = {!? 2, ? ■?, m} \ {k, ■■■, sk} for an integer number m > (s + 1)A\ J.J.Chen, G.J. Chang, D.F. Liu and X.D. Zhu studied the chromatic number of distance graphs G(Dm^s): Kemnitz and Marangio discussed the list chromatic number of integer distance graphs: D.F. Liu and X.D. Zhu studied the circular chromatic number of integer distance graphs.Professor B. Ballobds of university of Cambridge in British, a modern famous expert of the graph theory, claimed: every finite graph G can be isomorphic to some induced subgraph of an integer distance graph which is called the representation of G. Professor Y. Kohayakawa in Brazil, a PHD of university of Cambridge in 1991, studied this problem with a group and had a good work. So we can conjecture: it is possible to be given rise to a new component-the representation theory of graphs, in the near future. Therefore integer distance graphs become a focal point.In this paper, it is studied that the vertex arboricity and the vertex linear arboric-ity of distance graphs and the fractional vertex linear arboricity of graphs.We define a critical tree chromatic subgraph of a graph G to be a minimal subgraph of G with the same vertex arboricity as G. If a subgraph of G has the vertex arboricity va(G), it is called a tree chromatic subgraph of G. It is clear that if there is a finite tree chromatic subgraph of G, then there would be a critical tree chromatic subgraph (it can be obtained from a tree chromatic subgraph by deleting some vertices and edges).In Chapter 2, we study the vertex arboricity of distance graphs and obtain the following results.Conclusion 1. Hn—l<8 1, then va(G(R, D)) = n + 1 for an interval D between 1 and 8.Conclusion 2. There is a tree chromatic subgraph T(m, n) of G(R, D) for an interval D between 1 and 8 with l (s + l)k, we have the following results.Conclusion 4. For any s 6 {1,2,3} and m > 5, we haveva(G(DmXs)) = [m^ + 2l-Conclusion 5. Let m = 8/ + j > 6 with 0 < j < 8. Then va(G(Dm,2,i)) = r^j-^1 + 1 for j ? 7andva(G(DmX1)) = \j] + l or \j] + 2 for j = 7.Conclusion 6. Suppose that m = I2q + j > 9, 0 < ; < 12. Thenh 2, otherwise.Moreover, va (G (An,3,i)) = T^l + 1 for m = 12? + j with ; = 4,5. Conclusion 7. Let m = 10 10 with 0 < ; < 10. Then,90 I ^ \ for j = 1,2,3,5,6,10, forj=4,7,8,9.Moreover, va(G(DmX2)) = Pf1] + 1 for m = 10? + j > 10 with j = 1, 2, 3, 5,6,10.In Chapter 3, we obtain the following results for the vertex linear arboricity.Conclusion 8. (1) For nonnegative integers m and A; > 1, let D = {m + l,m + 2, ? ? ? ,m + k}. Then vla(G{D)) = \^] for m = 0 and vla(G{D)) < [^±§] + 1 for m > 1.(2) If A; e D and there is no any other multiple of k in D, then vla(G(D)) < k.Conclusion 9. Let D = {di, d2, ■■?} and n\di for i = 1,2, ? ? ?. Then A }) n nIt is proved that the following conclusions for special integer distance graphs G(DmXs).Conclusion 10. For any 5 e {1,2,3} and m > 6, we havevla(G(DmXs)) = r-^-1 + 1. Conclusion 11. For any positive integer m > 8, we have 1, if m = 8/ + l.I I I j j + 2, otherwise.Conclusion 12. Suppose that m = I2q + j > 9 with 0 < j < 12. Then771 + 21 j \j] +.2, for 0 < j < 3,4 m'3'1 1 [jl + 3, for 3 < j < 12.Conclusion 13. For any integer m = I2q + j > 10 with 0 < j < 12, we have+ 1 < vla{G{Dm,2t3)) 1 for all vertices x in G. The weight of a fractional path coloring is the sum of itsvalues, and the fractional vertex linear arboricity of the graph G is the minimum possible weight of a fractional path coloring, that is,n,for2nforn 2'forn- |, forn — 4. forvlaf(G) = min{ 2^ c(L) | c is a fractional path coloring of<7}.L€LF{G)For the fractional vertex linear arboricity, we have the following conclusions. Conclusion 14. For any complete n-partite graph G = K(mi,m2, ■■-, mn),= m-} = ? ? ? = 771^, = 771 > 3, = 7712 = ? ? ? = Tflu = 2,vlaf(G) = { |; formx = m2 = ??? = mn = 1,= ?Ti2 = ? ? ? = tUji-i = 3 and mn = 1, = 77i2 = ? ? ? = TUn-i = 3 and mn = 2.Conclusion 15. (1) For Dx = {1,2, ? ? ?,m}, vlas{G(Dx)) = ^±1.(2) For ￡>mrM = {2,3, ? ? ?, m}, 2!±2 < t;ia/(C?(￡>m,1,1)) < f + 1.(3) u/a/(G(P)) = 2 where P is the set of all prime numbers.Let Zn denote the additive group of integers modulo n. Suppose that C Q Zn\0 has the additional property that it is closed under additive inverse, that is, — c € C if and only if c 6 C. A circular graph is the graph G(Zn, C) with the vertex set Zn and i, j are adjacent if and only iti—jeC. In fact, the following graph Ga,b is the circular graph G(Za, C) with C = {-a + b, ■■■, -6,6, ? ? ?, a - b} {a > 2b).Conclusion 16. Let a and b be positive integers with a > 26. Ga 6 - 3 > 3.In a word, the main new results contained in this dissertation are as followings.1. For the focal graphs—distance graphs, we study their vertex arboricity, obtain a tree chromatic subgraph when the distance set is an interval, and generalize the result which obtained by Eggleton etal. For integer distance graphs, we obtain the exact values or sharp upper and lower bounds of the vertex arboricity in many cases.2. We study the vertex linear arboricity of integer distance graphs and obtain a series of good conclusions.3. We define the fractional vertex linear arboricity of general graphs and obtain its exact values for some classes of graphs.
|
PDF Full Text Request