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

DSpace/Manakin Repository

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

Show full item record

Title: Acyclic, k-intersection edge colourings and oriented colouring [HBNI Th 14]
Author: Narayanan, N.
Advisor: Subramanian, C.R.
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2009
Pages: 95p.
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.
URI: http://hdl.handle.net/123456789/169

Files in this item

Files Size Format View
narayanan.pdf 977.4Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account