L(t, 1)-COLOURING OF GRAPHS

L(t, 1)-COLOURING OF GRAPHS

P. Pandey, J. V. Kureethara

[PDF]

Abstract

One of the most famous applications of Graph Theory is in the eld of Channel Assignment Problems. There are varieties of graph colouring concepts that are used for dierent requirements of frequency assignments in communication channels. We introduce here L(t; 1)-colouring of graphs. This has its foundation in T-colouring and L(p; q)-colouring. For a given nite set T including zero, an L(t; 1)-colouring of a graph G is an assignment of non-negative integers to the vertices of G such that the dierence between the colours of adjacent vertices must not belong to the set T and the colours of vertices that are at distance two must be distinct. The variable t in L(t; 1) denotes the elements of the set T. For a graph G, the L(t; 1)-span of G is the minimum of the highest colour used to colour the vertices of a graph out of all the possible L(t; 1)-colourings. It is denoted by t;1(G). We study some properties of L(t; 1)-colouring. We also nd upper bounds of t;1(G) of stars and multipartite graphs.

Keywords

L(t; 1)-colouring, Communication networks, Radio frequency, Colour span