On Distance Two Labellings of Graphs

A distance two labelling (or coloring) is a vertex labelling with constraints on vertices within distance two, while the regular vertex coloring only has constraints on adjacent vertices (i.e. distance one). In this article, we consider three different types of distance two labellings. For each type, the minimum span, which is the minimum range of colors used, will be explored. Upper and lower bounds are obtained. Graphs that attain those bounds will be demonstrated. The relations among the minimum spans of these three types are studied.