The Problem Of Relaxed 2-distant Colourings Of Graphs

Let G(V,E)be a graph and let T1 be a set of nonnegative integers which contains 0.A T-colouring of a graph G is a function f from the set of vertices V(G)to nonnegative integers such that for any adjacent vertex u and v,|f(u)-f(v)|(?)T.Let r be a positive integer.When T = {0,1,...,r},then a T-colouring of G is also called a(r + 1)-distant colouring of G.The span of a(r + 1)-distant coloring f of G,denote by span(f)is max u,v∈V(G)|f(u)-f(v)|.The(r+ 1)-distant colouring span of a graph G,denoted by spr+1(G),is defined as min span(f),where f is taken over all possible(r + 1)-distant colorings of the graph G.Let t be a nonnegative integer.Let f be a mapping from V(G)to nonnegative integers.For each vertex u ∈V(G),let RNf(u)denote the set {v |uv∈ E(G),1 ≤|f(u)-f(v)|≤r}.If f satisfies:(1)|f(v)-f(w)| ≥ 1 for any two adjacent vertices v and w of G,(2)|RNf(u)|≤t for any vertex u of G,then f is called a t-relaxed(r + 1)-distant colouring of G.The t-relaxed(r + 1)-distant colouring span of a graph G,denote by spr+1(t)(G),is defined as minf span(f),where f is taken over all possible t-relaxed(r + 1)-distant colorings of the graph G.This thesis focuses on the case r = 1.It studies basic properties of t-relaxed 2-distant colorings of graphs and determines the t-relaxed 2-distant colouring spans of some special classes of graphs.Chapter 2 obtains lower and upper bounds for sp2(t)(G)and gives the graphs which attains the lower or upper bounds.Chapter 2 also determines sp2(t)(G)for paths,cycles and complete graphs.Let G be any complete multipartite graph.The 1-relaxed(resp.2-relaxed)2-distant colouring span of G is determined in Chapter 3(resp.Chapter 4).