Pair Labellings with Given Distance
Zoltán Füredi, Jerrold R. Griggs, Daniel J. Kleitman · SIAM Journal on Discrete Mathematics · 1989
Given a graph G and $d \in \mathbb{Z}^+$, the pair labelling number, $r(G,d)$, is defined to be the minimum n such that each vertex in G can be assigned a pair of numbers from $\{ 1, \cdots ,n\} $ in such a way that any two numbers used at adjacent vertices differ by at least d. A question of Roberts’ is answered by determining all possible values of $r(G,d)$ given the chromatic number of G. The answer follows by determining the chromatic number of the graph that has pairs of integers as vertices and edges joining pairs that are distance at least d apart. For general $t \in \mathbb{Z}^+$, the analogous questions for t-sets instead of pairs are considered. A solution for general t is conjectured which, for $d = 1$, reduces to Lovász's theorem on Kneser graphs.