A study on graph colouring with distance constraints

Abstract

In this dissertation, we have studied the variations of graph colouring based on distance constraints. For a given set T of non-negative integers including zero and a positive integer k, the L(T,1)-colouring of a graph G = (V,E) is a function c : V(G) and#8594; newline{0,1,2,...,k} such that |c(u)and#8722;c(v)| and#8712;/ T if the distance between u and v is 1 and |c(u)and#8722; newlinec(v)| and#8805; 1 whenever u and v are at distance 2. The L(T,1)-span, and#955;T,1(G) is the smallest positive integer k such that G admits an L(T,1)-Colouring. We have determined the newlineL(T,1)-span for some classes of graphs for set T whose elements are arranged in arithmetic progression. Further, for any general set T , we have found the bound for L(T,1)- span of a few classes of graphs. We use Python programming to colour certain classes of graphs concerning L(T,1)-colouring and fnd the value of L(T,1)-span. Next, we have explored equitable fractional open neighbourhood colouring, which is an extension of a specifc variation of L(h,k)-Colouring for h = 0 and k = 1. For a newlinepositive integer p, equitable fractional open neighbourhood colouring of a graph G is an newlineassignment of positive integers to the vertices of G such that for each vertex v and#8712;V(G), vertices of N(v) receives at least l1p|N(v)|m distinct colours and N(v) can be partitioned into k-classes V1,V2,...Vk such that ||Vi|and#8722; |Vj|| and#8804; 1 for every i and#824;= j and 1 and#8804; k and#8804; n. The minimum number of colours required to colour G such that it admits equitable fractional open neighbourhood colouring for a fxed p is called the equitable fractional open neighbourhood chromatic number, and#967;eq onc newlinep (G). We have studied some properties of equitable fractional open neighbourhood colouring and explored some classes of graphs which admit equitable fractional open neighbourhood colouring with land#8710;(pG)m colours. Further, we have introduced and examined a variation of perfect graphs, and#967;onc-perfect graphs, with respect to equitable fractional open neighbourhood colouring for the special case of p = 1.