Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-08T14:23:47.289Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs with Large Girth Not Embeddable in the Sphere

Published online by Cambridge University Press:  01 November 2007

PIERRE CHARBIT  and
STÉPHAN THOMASSÉ
PIERRE CHARBIT
Affiliation:
LIAFA, Université Paris 7 Denis Diderot, 2 place Jussieu, Case 7014, 75251 Paris Cedex 05, France (e-mail: pierre.charbit@liafa.jussieu.fr)
STÉPHAN THOMASSÉ
Affiliation:
LIRMM, Université Montpellier 2, 161 rue Ada, 34392 Montpellier Cedex 5, France (e-mail: thomasse@lirmm.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 6 , November 2007 , pp. 829 - 832
Copyright
Copyright © Cambridge University Press 2007

References

[1]Brandt, S. and Thomassé, S. Dense triangle-free graphs are four-colorable: A solution to the ErdHős–Simonovits problem. to appear in J. Combin Theory Ser. B.Google Scholar
[2]ErdHős, P. (1979) Problems and results in graph theory and combinatorial analysis. In Graph Theory and Related Topics (Proc. Conf. Waterloo, 1977), Academic Press, New York, pp. 153–163.Google Scholar
[3]Goemans, M. X. and Williamson, D. P. (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42 1115–1145.CrossRefGoogle Scholar
[4]Karger, D., Motwani, R. and Sudan, M. (1998) Approximate graph coloring by semidefinite programming. J. Assoc. Comput. Mach. 45 246–265.CrossRefGoogle Scholar
[5]Larman, D. G. (no 1978) A triangle-free graph which cannot be $\sqrt 3$-imbedded in any Euclidean unit sphere. J. Combin. Theory Ser. A 24 162–169.CrossRefGoogle Scholar
[6]NeĚsetĚril, J. and Rosenfeld, M. (1997) Embedding graphs in Euclidean spaces: An exploration guided by Paul Erdos. Geombinatorics 6 143–155.Google Scholar
[7]Rödl, V. (1984) On combinatorial properties of spheres in Euclidean spaces. Combinatorica 4 345–349.CrossRefGoogle Scholar
[8]Rosenfeld, M. (1982) Triangle-free graphs that are not $\sqrt 3$-embeddable in Sd. J. Combin. Theory Ser. B 33 191–195.CrossRefGoogle Scholar