A linear time algorithm to compute square of interval graphs and their colouring

The square of a graph G=(V,E)G=(V,E), denoted by G2G2, is a graph on the same vertex set V(G)V(G) such that two vertices xx and yy are adjacent in G2G2 if and only if there is a path of length one or two between xx and yy in GG. In this article, a new linear time algorithm is presented to compute G2G2 from GG when GG is an interval graph. Also a linear time algorithm is designed to find all the maximal cliques of G2G2 from GG. Application of square of interval graphs in the field of L(h,k)L(h,k)-labelling problem is also discussed. Finally, it is shown that L(1,1)L(1,1)-labelling number of an interval graph can be computed in linear time.