Graphs with Large Girth Not Embeddable in the Sphere
Pierre Charbit, Stéphan Thomassé · Combinatorics Probability Computing · 2007
In 1972, Rosenfeld asked if every triangle-free graph could be embedded in the unit sphere Sd in such a way that two vertices joined by an edge have distance more than $\sqrt 3$ (ie, distance more than 2π/3 on the sphere). In 1978, Larman [LAR] disproved this conjecture, constructing a triangle-free graph for which the minimum length of an edge could not exceed $\sqrt{8/3}$ . In addition, he conjectured that the right answer would be $\sqrt{2}$ , which is not better than the class of all graphs. Larman'sconjecture was independently proved by Rosenfeld [MR] and Rödl [VR[. In this last paper it was shown that no bound better than $\sqrt 2$ can be found for graphs with arbitrarily large odd girth. We prove in this paper that this is stilltrue for arbitrarily large girth. We discuss then the case of triangle-free graphs with linear minimum degree.