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

doi:10.37236/3527

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 journal › Article › peer-review

14 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 language	English (US)
Journal	Electronic Journal of Combinatorics
Volume	22
Issue number	1
DOIs	https://doi.org/10.37236/3527
State	Published - Mar 23 2015
Externally published	Yes

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

Access to Document

10.37236/3527

Cite this

@article{cfd6728bf21b46d2a5117d37b8b97d26,

title = "A de Bruijn-Erd{\H o}s theorem for chordal graphs",

abstract = "A special case of a combinatorial theorem of De Bruijn and Erd{\H o}s asserts that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chv{\'a}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.",

keywords = "Combinatorial geometry, Extremal combinatorics, Metric space",

author = "Laurent Beaudou and Adrian Bondy and Xiaomin Chen and Ehsan Chiniforooshan and Maria Chudnovsky and Va{\v s}ek Chv{\'a}tal and Nicolas Fraiman and Yori Zwols",

year = "2015",

month = mar,

day = "23",

doi = "10.37236/3527",

language = "English (US)",

volume = "22",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - A de Bruijn-Erdős theorem for chordal graphs

AU - Beaudou, Laurent

AU - Bondy, Adrian

AU - Chen, Xiaomin

AU - Chiniforooshan, Ehsan

AU - Chudnovsky, Maria

AU - Chvátal, Vašek

AU - Fraiman, Nicolas

AU - Zwols, Yori

PY - 2015/3/23

Y1 - 2015/3/23

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

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

KW - Combinatorial geometry

KW - Extremal combinatorics

KW - Metric space

UR - http://www.scopus.com/inward/record.url?scp=84925379765&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84925379765&partnerID=8YFLogxK

U2 - 10.37236/3527

DO - 10.37236/3527

M3 - Article

AN - SCOPUS:84925379765

SN - 1077-8926

VL - 22

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

ER -

A de Bruijn-Erdős theorem for chordal graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this