Annulus graphs in ${\mathbb{R}}^d$

Abstract

A $d$-dimensional annulus graph with radii $R_1$ and $R_2$ (here $R_2\ge R_1\ge 0$) is a graph embeddable in ${\mathbb{R}}^d$ so that two vertices $u$ and $v$ form an edge if and only if their images in the embedding are at distance in the interval $[R_1,R_2]$. In this paper we show that the family ${\mathcal{A}}_d(R_1,R_2)$ of $d$-dimensional annulus graphs with radii $R_1$ and $R_2$ is uniquely characterised by $R_2/R_1$ when this ratio is sufficiently large. Moreover, as a step towards a better understanding of the structure of ${\mathcal{A}}_d(R_1,R_2)$, we show that ${\sup }_{G\in {\mathcal{A}}_d(R_1,R_2)}\chi (G)/\omega (G)$ is given by $\exp (O(d))$ for all $R_1,R_2$ satisfying $R_2\ge R_1>0$ and also $\exp (\Omega (d))$ if moreover $R_2/R_1\ge 1.2$.

17 pages, 6 figures