Tensor Product and Acyclic Edge Colouring

Abstract

"The assignment of colours to the edges of graph G such that no two adjacent edges get the same colour and there is no 2-coloured cycle in G is known as Acyclic Edge Colouring. The minimum number of colours needed to acyclically edge colour the graph is known as acyclic chromatic index and is denoted by a0(G). The difference between a0(G) and 4(G) is known as the gap of the graph. Determining the value of a0(G) either algorithmically or theoretically has been a very difficult problem. It belongs to the class of NP-complete problems. The value of a0(G) has not yet been determined even for the highly structured class of graphs like complete graphs.Determining the exact values of a0(G) even for very special classes of graphs is still open. Tensor Product, also known as Kronecker Product is a special type of graph product. Any graph that can be represented as a tensor product has the same number of irreducible factors, even though the factor graphs may be different for different factorizations. There exists an algorithm that recognizes tensor product graphs in polynomial time and finds a factorization for the same. This thesis addresses the problem of finding a0(G) for a graph G which is a tensor product of either K2, paths or cycles. We have provided optimal and sub-optimal colouring techniques for colouring the tensor product graph, whose factors are either gap 0 or gap 1 graphs. This thesis focuses on the tensor product graphs whose factors are specific gap 0 and gap 1 graphs which are edges, paths or cycles. This can later be extended to arbitrary gap 0 and gap 1 graphs."