A de Bruijn-Erdős theorem for chordal graphs

Laurent Beaudou, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, Maria Chudnovsky, Vašek Chvátal, Nicolas Fraiman, Yori Zwols

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


A special case of a combinatorial theorem of De Bruijn and Erdős 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.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Issue number1
StatePublished - Mar 23 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Combinatorial geometry
  • Extremal combinatorics
  • Metric space


Dive into the research topics of 'A de Bruijn-Erdős theorem for chordal graphs'. Together they form a unique fingerprint.

Cite this