
etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2005/2263

Title:  Acyclic Edge Coloring Of Graphs 
Authors:  Basavaraju, Manu 
Advisors:  Chandran, L Sunil 
Keywords:  Graph  Coloring Graph Theory Graphs  Acyclic Edge Coloring Subcubic Graphs 2Degenerate Graphs Planar Graphs Acyclic Edge Coloring Dense Graphs 
Submitted Date:  Sep2010 
Series/Report no.:  G24692 
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 nonregular 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 2degenerate 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 edgeconnectivity 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 2degenerate graphs and posed the problem of proving the conjecture for 2degenerate graphs as an open problem. In fact they have also derived an upper bound of Δ+1 for seriesparallel graphs [35], which is a slightly bigger subclass of 2degenerate graphs. We proved that 2degenerate 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. 
Abstract file URL:  http://etd.ncsi.iisc.ernet.in/abstracts/2885/G24692Abs.pdf 
URI:  http://hdl.handle.net/2005/2263 
Appears in Collections:  Computer Science and Automation (csa)

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.
