Acyclic, k-intersection edge colourings and oriented colouring [HBNI Th14]

Abstract

Three graph colouring problems are studied in this thesis with the main focus on 'acyclic edge colouring problem'. The first part of this thesis deals with some classes of graphs and improved upper bounds are obtained. The second part deals with k-intersection edge colouring. It aims to find the minimum number of colours that are sufficient to colour the edges such that for any pair of adjacent vertices, the number of common colours received on the edges incident on them is at most k. An upper bound of O(Delta^2 / k) is obtained and shown that this bound is tight for complete graphs. The oriented vertex colouring of graphs is focused in the third part of the thesis. An improved upper and lower bounds on oriented chromatic number for certain classes of graphs and products of graphs are obtained.