Researches On Some Arboricities Of Graphs

A proper total k-coloring of a graph G is a coloring of V(G) ? E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number, denoted by x"(G), is the smallest integer k such that G has a proper total k-coloring. A proper vertex coloring or a proper edge coloring of G can be similarly defined, respectively. We use ?(C) and ?'(G) to denote the vertex chromatic number and edge chromatic number of G, respectively. The concept of arboricity can be viewed as a coloring (not necessarily be proper) of a graph, where each color class induces a forest. A few types of arboricities of graphs are considered in this dissertation:linear arboricity, linear k-arboricity, k-star arboricity, total arboricity, list total arboricity and strong equitable vertex arboricity of graphs. The main contents are summarized as follows:(1) Linear arboricity of graphs. A linear forest is a forest in which each component is a path. The linear arboricity of a graph G, denoted by la(G), is the smallest integer m such that G can be decomposed into m linear forests. The linear arboricity of the Cartesian products of a complete graph and a path, a complete graph and a cycle, two complete graphs are determined in this dissertation.(2) Linear k-arboricity of graphs. A linear k-forest is a forest in which each component is a path of length at most k. The linear k-arboricity of a graph G, denoted by lak(G), is the smallest integer m such that G can be decomposed into m linear k-forests. The linear 2-arboricities of the Cartesian products of two cycles are totally determined. In addition, The upper bounds for the linear 2-arboricities of some classes of planar graphs are also provided in this dissertation.(3) k-star arboricity of graphs. A star is a tree with at most one vertex with degree larger than one. A k-star forest is a forest whose components are all stars of order at most k+1. The k-star arboricity of a graph G, denoted by sak(G), is the smallest integer m such that G can be decomposed into m k-star forests. The upper and lower bounds for k-star arboricities of subcubic graphs and trees are obtained. Besides, two algorithms relevant to this problem are also designed.(4) Total arboricity and list total arboricity of graphs. A total k-coloring f of a graph G (not necessarily be proper) is called an arboritic total k-coloring if each color class induces a forest in the total graph. The total arboricity of a graph G, denoted by p"(G), is the smallest integer k such that G has an arboritic total k-coloring. A list L to the elements of a graph G is the assignment of a color set L(x) to each element x of G. Given a list L of G, an arboritic total coloring f is an arboritic list total coloring if f(x)?L(x) for every elemen t x? V(G) U E(G). A graph G is said to be arboritically totally k-choosable if G has an arboritic list total coloring from all possible lists L(x) with |L(x)|?k. The smallest integer k such that G is arboritically totally k-choosable is the list total arboricity of G, which is denoted by ?l"[(G). The concepts of total arboricity and list total arboricity are introduced by Hetherington. He proposed a conjecture on total arboricity:for any graph G, [?(G+1/)A2]??"(G)?[?(G)+2/2]. The total arboricities of complete graph Kn and complete bipartite graph Kn,n are determined, implying that the conjecture holds for these graphs. The upper bound for the list total arboricity of Halin graphs is also obtained. The total arboricity of planar graphs is studied in this dissertation. It is proved that the total arboricity conjecture holds for the planar graphs with ?(G)?13 and planar graphs with ?(G)?7 and without 4-cycles.(5) Strong equitable vertex arboricity of graphs. A (t, k)-tree-coloring is a t-coloring f of vertices of a graph G such that each component of the subgraph induced by each color class is a tree of maximum degree at most k. An equitable (t, k)-tree-coloring is a (t,k)-tree-coloring such that the sizes of any two color classes differ by at most one. The strong equitable vertex k-arboricity of G, denoted by vak?(G), is the smallest integer t such that G has an equitable (t',k)-tree-coloring for every t'?t. This concept was introduced by Wu et al. They proposed a conjecture:for every planar graph G, v???(G)=O(1). The strong equitable vertex 1-arboricity of complete bipartite graph Kn,n is considered. Besides, the upper bounds for the strong equitable vertex ?-arboricities of two classes of planar graphs are provided, which confirm the conjecture above.