A Study on Acyclic Edge Coloring and Domination Number of a Graph

Abstract

Let G =(V,E) be a graph with n vertices and let C be a given set of colors. A proper edge coloring of the graph G with the colors from the setC is a function f : E →C such that f(e1) ̸ = f(e2) for any adjacent edges e1 and e2. An acyclic edge coloring of a graph is a proper edge coloring without any bichro matic cycles. The acyclic chromatic index of a graph G denoted by a′(G), is the min imum positive integer k such that G has an acyclic edge coloring with k colors. It was conjectured by Fiamˇc´ ık (1978) (and independently by Alon, Sudakov and Zaks (2001)) that a′(G) ≤ ∆+2 for any graph G with maximum degree ∆. Linear arboricity of a graph G, denoted by la(G), is the minimum number of linear forests into which the edges of G can be partitioned. It was conjectured by Akiyama, Exoo and Harary (1980) that for any graph G, la(G) ≤ ⌈∆+1 2 ⌉. Agraph is said to be chordless if no cycle in the graph contains a chord. By a result of Basavaraju and Chandran (2010), if G is chordless, then a′(G) ≤ ∆+1. Machado, de Figueiredo and Trotignon (2013) proved that the chromatic index of a chordless graph is ∆ when ∆ ≥ 3. In this thesis, it is proved that for any chordless graph G, a′(G) = ∆, when ∆ ≥ 3. One can see that this is an improvement over the result of Machado et al. (2013), since any acyclic edge coloring is also a proper edge coloring and we are using the same number of colors. The thesis also provides the sketch of a polynomial-time algorithm that takes a chordless graph G as an input and returns an optimal acyclic edge coloring of G as the output. As a byproduct, one can prove that la(G) = ⌈∆ 2⌉, when ∆ ≥3. To obtain the result on the acyclic chromatic index of a chordless graph, an extremal structure in chordless graphs has been proved which is a refinement of the structure given by Machado et al. (2013) in the case of chromatic index. This extremal structure might be of independent interest. Agraph G is said to be k-degenerate if every subgraph of G has a vertex of degree at most k. Basavaraju and Chandran (2010) proved that the acyclic edge coloring con jecture is true for 2-degenerate graphs. In the thesis, it is proved that for a 3-degenerate graph G, a′(G) ≤ ∆+5, thereby bringing the upper bound closer to the conjectured bound. The thesis also considers the class of k-degenerate graphs with k ≥ 4 and improves iii the existing upper bound given by Fiedorowicz (2011) for the acyclic chromatic index of a k-degenerate graph. Aset of vertices D in graph G is said to be a dominating set if every vertex which is not in D is adjacent to a vertex in D. The size of a minimum dominating set of G is said to be the domination number of G and is denoted by γ(G). A classical upper bound for the domination number of a graph G having no iso lated vertices is ⌊n 2 ⌋. However, for several families of graphs, we have γ(G) ≤ ⌊√ n⌋ which gives a substantially improved upper bound. By the multiplicative version of the Nordhaus-Gaddum type result for the domination number of a graph, for any graph G with n vertices and Gbeing the complement of G, we have γ(G)γ( will imply that for every graph G, either γ(G) ≤ ⌊√ n⌋ or γ( G) ≤n. This result G) ≤⌊√ n⌋ or both. The thesis presents some conditions necessary for a graph G to have γ(G) ≤ ⌊√ and some conditions sufficient for a graph G to have γ(G) ≤ ⌊√ of all connected graphs G with γ(G) = ⌊√ n⌋, n⌋. A characterization n⌋ is also provided. Further, the thesis also provides proof for the statement that if the condition: rad(G) =diam(G) =rad( G)=diam( G)=2 is not satisfied for a graph G, then the task of deciding whether it is γ(G) ≤ ⌊√ G) ≤⌊√ γ( n⌋ or n⌋ can be done in polynomial time. The thesis concludes with a conjec ture that a slightly weaker decision problem can be solved in polynomial time for any arbitrary graph. Along with the above mentioned results, the thesis also introduces a new termi nology of t-complementary self-centered graphs and a new concept of freeable colors, thereby contributing to the literature of acyclic edge coloring and the domination in graphs. This concept of freeable colors turns out to be a very useful tool for proving the upper bounds on the acyclic chromatic index.