Linear Coloring Of Graphs

Let G = (V, E) be a finite, simple and undirected graph with the set of vertices V and the set of edges E, and C = {1,2,…, k}, a set of k colors. A proper k-coloring of G is a mapping from V to C such that no adjacent vertices receive the same color. If G has a proper k-coloring, then G is said to be k-colorable.The chromatic index, denoted byχ(G), is the least non-negative integer k such that G is k-colorable. A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G.In 1998, Yuster^[1] first investigated the linear coloring of graphs by showing lc(G) = O(Δ^?) for any graph G and constructing a graph G such that lc(G) =Ω(Δ^?). Indeed, this concept is a special case of acyclic coloring of G. The acyclic coloring of G was introduced by Grunbaum^[2], a proper vertex coloring of G is called acyclic if any two color classes induce a forest.In this master thesis, our theorems are extension and improvement of the precedent results, and investigate the graph of nonnegative characteristic, planar graph and the graph with smaller maximum degree. We useΔ(G) and g(G) to denote, respectively, the maximum degree and girth of G.In Chapter 1, we collect some basic notions used in the thesis and give a chief survey in this direction. Main results in the thesis are stated. In Chapter 2, we prove that:(1) Every graph of nonnegative characteristic G has lc(G) = (?) + 1 if there is a pair (Δ, g)∈{(13,7), (9,8), (7,9), (5,10), (3,13)} such that G satisfiesΔ(G)≥A and g(G)≥g.In Chapter 3, we obtain that:(1) Every plane graph G has lc(G) = (?)+ 1 if G satisfies A(G)≥3 and g(G)≥12 orΔ(G)≥7 and g(G)≥8.In Chapter 4, we investigate some graphs with smaller maximum degree, and we obtain that:(1) If G is a graph withΔ(G)≤5, then lc(G)≤14.(2) If G is a graph withΔ(G)≤4, then lc(G)≤8.