Application Of Local Cut Lemma In Acyclic Dyeing Of Linear Indian And K_? Images Of Directed Graphs

Local Cut Lemma (the LCL for short) was introduced by Bernshteyn, it is a generalization of the Lovasz Local Lemma, (the LLL for short) and inspired by its algorithm—entropy compression method. Their proofs are probabilistic and mainly apply on graph colouring problems. With the study of trees, Harary [29] introduced the concept of linear arboricity in 1970s. A linear directed forest is a directed graph in which every component is a directed path. The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and Peroche conjecture that, la(D) = d + 1. Afterwards He, Li, Bai and Sun [31] considered the linear arboricity for complete symmetric digraphs and regular digraphs with high directed girth and they improve some well-known results la(D) = d + 1, when d-regular digraph D with directed girth g > 8.0786d. In this paper, we improved their result and get when d - 1, la(D) = d, + 1 for all d-regular directed graphs, when d ? 2) la(D) = d + 1 for these d-regular graphs satisfying g > 8d. A vertex coloring of a graph G is called acyclic coloring if it is a proper vertex coloring and every cycle receives at least three colors. The acyclic chromatic number of G is the least number of colors in an acyclic coloring of G. The notion of acyclic vertex coloring was first introduced by Grunbaum [24]. Alon, McDiarmid,and Reed [6] considered the acyclic chromatic number of K? (have no copy of K2,r+1). The best known general bound of K?- is ?a(G) ?1 + ?(1 + (?) [22]. In this paper we use Local Cut Lemma to show that when ? = 1, 2, 3, the result can be improved respectively to Xa(G) ? 3.2?; ?a(G) < (1 + (?));Xa(G) ? 4?.This paper is divided into five chapters. The first chapter is an introduction of the origin and development process of graphs theory, it focuses on some representative problems of the various development stages of graph theory. The second chapter is divided into two sections,the first section is an introduction of some definitions in this paper, and the second section is a summary of development on linear arboricity and acyclic coloring problem. The third chapter is made up of the development on LLL and entropy compression, the applications of entropy compression on graph coloring, and the second section focus on the definition of Local Cut Lemma and its applications, such as nonrepetitive coloring, acyclic edge coloring with maximum degree A and so on. The fourth chapter is the most important part of this paper, composed of two sections, respectively works on the applications of LCL on the linear arboricity of digraph and the acyclic coloring on K? graph. The final chapter is an summary for this paper.