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 journalArticle

5 Scopus citations

Abstract

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
Volume22
Issue number1
DOIs
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

Keywords

  • Combinatorial geometry
  • Extremal combinatorics
  • Metric space

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

  • Cite this

    Beaudou, L., Bondy, A., Chen, X., Chiniforooshan, E., Chudnovsky, M., Chvátal, V., Fraiman, N., & Zwols, Y. (2015). A de Bruijn-Erdős theorem for chordal graphs. Electronic Journal of Combinatorics, 22(1). https://doi.org/10.37236/3527