Please use this identifier to cite or link to this item:
http://hdl.handle.net/10603/533986
Title: | A study on graph colouring with distance constraints |
Researcher: | Pandey, Priyanka |
Guide(s): | Joseph, Mayamma |
Keywords: | and#967;onc-perfect graphs, colour span, equitable fractional open neighbourhood colouring, Graph colouring, L(h,k)-colouring, L(T,1)-colouring, Mathematics Mathematics Applied Physical Sciences T -colouring, |
University: | CHRIST University |
Completed Date: | 2023 |
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. |
Pagination: | xiv, 140p.; |
URI: | http://hdl.handle.net/10603/533986 |
Appears in Departments: | Department of Mathematics and Statistics |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
01_title.pdf | Attached File | 174.4 kB | Adobe PDF | View/Open |
02_prelim pages.pdf | 833.75 kB | Adobe PDF | View/Open | |
03_abstract.pdf | 108.47 kB | Adobe PDF | View/Open | |
04_contents.pdf | 106.57 kB | Adobe PDF | View/Open | |
05_chapter1.pdf | 222.27 kB | Adobe PDF | View/Open | |
06_chapter2.pdf | 380.21 kB | Adobe PDF | View/Open | |
07_chapter3.pdf | 172.92 kB | Adobe PDF | View/Open | |
08_chapter4.pdf | 214.1 kB | Adobe PDF | View/Open | |
09_chapter5.pdf | 254.35 kB | Adobe PDF | View/Open | |
10_annexures.pdf | 110.58 kB | Adobe PDF | View/Open | |
80_recommendation.pdf | 427.84 kB | Adobe PDF | View/Open |
Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).
Altmetric Badge: