Graphs with Large Girth Not Embeddable in the Sphere

Pierre Charbit 1 Stéphan Thomassé 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In 1972, M. Rosenfeld asked if every triangle-free graph could be embedded in the unit sphere $S^d$ in such a way that two vertices joined by an edge have distance more than $\sqrt 3$ (i.e. distance more than $2\pi/3$ on the sphere). In 1978, D. Larman~\cite{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's conjecture was independently proved by M. Rosenfeld~\cite{MR} and V. R\H{o}dl~\cite{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 still true for arbitrarily large girth. We discuss then the case of triangle-free graphs with linear minimum degree.
Type de document :
Article dans une revue
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2007, 16 (6), pp.829-832. 〈10.1017/S0963548307008528〉
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250083
Contributeur : Stephan Thomasse <>
Soumis le : mercredi 20 février 2008 - 22:03:14
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 17 mai 2010 - 20:02:30

Fichier

Identifiants

Collections

Citation

Pierre Charbit, Stéphan Thomassé. Graphs with Large Girth Not Embeddable in the Sphere. Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2007, 16 (6), pp.829-832. 〈10.1017/S0963548307008528〉. 〈lirmm-00250083〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

118