Acyclic Edge Coloring Of Graphs

Abstract

A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum number of colors required to acyclically edge color G. The primary motivation for this thesis is the following conjecture by Alon, Sudakov and Zaks [7] (and independently by Fiamcik [22]): Acyclic Edge Coloring Conjecture: For any graph G, a’ (G) ≤ Δ(G)+2. The following are the main results of the thesis: 1 From a result of Burnstein [16], it follows that any subcubic graph can be acyclically edge colored using at most 5 colors. Skulrattankulchai [38] gave a polynomial time algorithm to color a subcubic graph using Δ + 2 = 5 colors. We proved that any non-regular subcubic graph can be acyclically colored using only 4 colors. This result is tight. This also implies that the fifth color, when needed is required only for one edge. 2 Let G be a connected graph on n vertices, m ≤ 2n - 1 edges and maximum degree Δ ≤ 4, then a’ (G) ≤ 6. This implies that graph of maximum degree 4 are acyclically edge colorable using at most 7 colors. 3 The earliest result on acyclic edge coloring of 2-degenerate graphs was by Caro and Roditty [17], where they proved that a’ (G) ≤ Δ + k - 1, where k is the maximum edge connectivity, defined as k = maxu,vε V(G)λ(u,v), where λ(u,v)is the edge-connectivity of the pair u,v. Note that here k can be as high as Δ. Muthu,Narayanan and Subramanian [34] proved that a’ (G) ≤ Δ + 1for outerplanar graphs which are a subclass of 2-degenerate graphs and posed the problem of proving the conjecture for 2-degenerate graphs as an open problem. In fact they have also derived an upper bound of Δ+1 for series-parallel graphs [35], which is a slightly bigger subclass of 2-degenerate graphs. We proved that 2-degenerate graphs are Δ+1colorable. 1 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of 2Δ+29 for planar graphs. Independently Hou, Wu, GuiZhen Liu and Bin Liu [29] gave an upper bound of max(2Δ - 2,Δ+ 22). We improve this upper bound to Δ+12, which is the best known bound at present. 2 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of Δ+6for triangle free planar graphs. We improve the bound to Δ+3, which is the best known bound at present. 3 We have also worked on lower bounds. Alon et.al. [7], along with the acyclic edge coloring conjecture, also made an auxiliary conjecture stating that Complete graphs of 2n vertices are the only class of regular graphs which require Δ+2colors. We disproved this conjecture by showing infinite classes of regular graphs other than Complete Graphs which require Δ+2colors. Apart from the above mentioned results, this thesis also contributes to the acyclic edge coloring literature by introducing new techniques like Recoloring, Color Exchange (exchanging colors of adjacent edges), circular shifting of colors on adjacent edges (derangement of colors). These techniques turn out to be very useful in proving upper bounds on the acyclic edge chromatic number.