L(3,2,1)- and L(4,3,2,1)-labeling problems on interval graphs

For a given graph G=(V,E), the L(3,2,1)- and L(4,3,2,1)-labeling problems assign the labels to the vertices of G. Let Z∗ be the set of non-negative integers. An L(3,2,1)- and L(4,3,2,1)-labeling of a graph G is a function f:V→Z∗ such that |f(x)−f(y)|≥k−d(x,y), for k=4,5 respectively, where d(x,y) represents the distance (minimum number of edges) between the vertices x and y, and 1≤d(x,y)≤k−1. The L(3,2,1)- and L(4,3,2,1)-labeling numbers of a graph G, are denoted by λ3,2,1(G) and λ4,3,2,1(G) and they are the difference between highest and lowest labels used in L(3,2,1)- and L(4,3,2,1)-labeling respectively. In this paper, for an interval graph G, it is shown that λ3,2,1(G)≤6Δ−3 and λ4,3,2,1(G)≤10Δ−6, where Δ represents the maximum degree of the vertices of G. Also, two algorithms are designed to label an interval graph by maintaining L(3,2,1)- and L(4,3,2,1)-labeling conditions. The time complexities of both the algorithms are O(nΔ2), where n represent the number of vertices of G.