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

Abstract

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
Loading...

Dates and versions

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

Licence

Identifiers

  • HAL Id : hal-01263335 , version 1

Cite

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

Share

Gmail Mastodon Facebook X LinkedIn More