A De Bruijn–Erdős theorem for chordal graphs - Sorbonne Université Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2015

A De Bruijn–Erdős theorem for chordal graphs


A special case of a combinatorial theorem of De Bruijn and Erd˝ os asserts that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvátal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces induced by connected chordal graphs.
Fichier principal
Vignette du fichier
1201.6376v1.pdf (81.97 Ko) Télécharger le fichier
Origin Publication funded by an institution

Dates and versions

hal-01263335 , version 1 (27-01-2016)



  • HAL Id : hal-01263335 , version 1


Laurent Beaudou, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, Maria Chudnovsky, et al.. A De Bruijn–Erdős theorem for chordal graphs. The Electronic Journal of Combinatorics, 2015, 22 (1), pp.1.70. ⟨hal-01263335⟩
325 View
190 Download


Gmail Mastodon Facebook X LinkedIn More