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

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