A De Bruijn–Erdős Theorem for Chordal Graphs

Laurent Beaudou, Adrian Bondy, Xiaohong Chen, Ehsan Chiniforooshan, Maria Chudnovsky, Vašek Chvátal, Nicolás Fraiman, Yori Zwólš

Type: Article

Publication Date: 2015-03-23

Citations: 19

DOI: https://doi.org/10.37236/3527

View Chat PDF

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 Chávtal 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.

Locations

The Electronic Journal of Combinatorics - View - PDF
arXiv (Cornell University) - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	A De Bruijn–Erdős theorem for chordal graphs	2015	Laurent Beaudou Adrian Bondy Xiaohong Chen Ehsan Chiniforooshan Maria Chudnovsky Vasek Chvâtal Nicolás Fraiman Yori Zwólš
+	A De Bruijn-Erdos theorem for chordal graphs	2012	Laurent Beaudou Adrian Bondy Xiaohong Chen Ehsan Chiniforooshan Maria Chudnovsky Vasek Chvâtal Nicolás Fraiman yori Zwols
+	A De Bruijn-Erdos theorem for 1-2 metric spaces	2012	Vašek Chvátal
+	A De Bruijn-Erdos theorem for 1-2 metric spaces	2012	Vašek Chvátal
+ PDF Chat	A de Bruijn - Erdos theorem and metric spaces	2011	Ehsan Chiniforooshan Vašek Chvátal
+	A de Bruijn - Erdős theorem and metric spaces	2009	Ehsan Chiniforooshan Vašek Chvátal
+	Problems related to a de Bruijn–Erdös theorem	2007	Xiaohong Chen Vašek Chvátal
+	On a Generalization of the de Bruijn-Erdos Theorem	2014	Cathryn Supko
+	Problems related to a de Bruijn - Erdős theorem	2006	Xiaohong Chen Vašek Chvátal
+	A de Bruijn - Erd\H{o}s theorem and metric spaces	2009	Ehsan Chiniforooshan Vašek Chvátal
+	A new class of graphs that satisfies the Chen-Chvátal Conjecture	2016	P Aboulker Martı́n Matamala Paul Rochet José Zamora
+	A new class of graphs that satisfies the Chen-Chv\'atal Conjecture	2016	Pierre Aboulker Martı́n Matamala Paul Rochet José Zamora
+	Towards a de Bruijn-Erd\H os theorem in the $L_1$-metric	2012	Ida Kantor Balázs Patkós
+	The Chen–Chvátal conjecture for metric spaces induced by distance-hereditary graphs	2014	Pierre Aboulker Rohan Kapadia
+	Problems related to a de Bruijn - Erd\H{o}s theorem	2006	Xiaohong Chen Vašek Chvátal
+ PDF Chat	A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture	2017	P Aboulker Martı́n Matamala Paul Rochet José Zamora
+	Graphs with no induced house nor induced hole have the de Bruijn-Erdős property.	2020	Pierre Aboulker Laurent Beaudou Martı́n Matamala José Zamora
+	Graphs with no induced house nor induced hole have the de Bruijn-Erdős property	2020	P Aboulker Laurent Beaudou Martı́n Matamala José Zamora
+	Graphs with no induced house nor induced hole have the de Bruijn–Erdös property	2022	Pierre Aboulker Laurent Beaudou Martı́n Matamala José Zamora
+	A de Bruijn and Erdös property in quasi-metric spaces with four points	2023	Gabriela Araujo‐Pardo Martı́n Matamala José Zamora

Cited by (14)

Action	Title	Year	Authors
+ PDF Chat	A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture	2017	P Aboulker Martı́n Matamala Paul Rochet José Zamora
+	The Chen–Chvátal conjecture for metric spaces induced by distance-hereditary graphs	2014	Pierre Aboulker Rohan Kapadia
+	A de Bruijn–Erdös Theorem for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e20" altimg="si6.svg"><mml:mrow><mml:mo>(</mml:mo><mml:mi>q</mml:mi><mml:mo>,</mml:mo><mml:mi>q</mml:mi><mml:mo linebreak="goodbreak" linebreakstyle="after">−</mml:mo><mml:mn>4</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math>-graphs	2019	Rainer Schräder Lukas Stenmans
+ PDF Chat	Chen and Chvátal’s conjecture in tournaments	2021	Gabriela Araujo‐Pardo Martı́n Matamala
+ PDF Chat	Betweenness structures of small linear co-size	2022	Péter G. N. Szabó
+ PDF Chat	Lower general position sets in graphs	2024	Gabriele Di Stefano Sandi Klavžar Aditi Krishnakumar James Tuite Ismael G. Yero
+ PDF Chat	Lines, Betweenness and Metric Spaces	2016	Pierre Aboulker Xiaohong Chen Guangda Huzhang Rohan Kapadia Cathryn Supko
+	Graphs with no induced house nor induced hole have the de Bruijn–Erdös property	2022	Pierre Aboulker Laurent Beaudou Martı́n Matamala José Zamora
+	Lines in metric spaces: universal lines counted with multiplicity	2018	Martı́n Matamala José Zamora
+	Solution of the Chen-Chvátal conjecture for specific classes of metric spaces	2021	Juan A. Rodríguez‐Velázquez
+	Chen and Chv\'atal's Conjecture in tournaments	2019	Gabriela Araujo‐Pardo Martı́n Matamala
+ PDF Chat	Bisplit graphs satisfy the Chen-Chvátal conjecture	2018	Laurent Beaudou Giacomo Kahn Matthieu Rosenfeld
+	Extremal Problems on Finite Sets and Posets	2015	Casey Tompkins
+	A Characterization of Uniquely Representable Graphs	2017	Péter G. N. Szabó

Citing (11)

Action	Title	Year	Authors
+ PDF Chat	Sylvester?Gallai Theorem and Metric Betweenness	2004	Vasek Chv�tal
+ PDF Chat	A de Bruijn - Erdos theorem and metric spaces	2011	Ehsan Chiniforooshan Vašek Chvátal
+	The geometry of geodesics	1955	Herbert Busemann
+	Problems related to a de Bruijn–Erdös theorem	2007	Xiaohong Chen Vašek Chvátal
+ PDF Chat	The Sylvester-Chvatal Theorem	2005	Xiaohong Chen
+	Introduction to Geometry	1969	H. S. M. Coxeter
+ PDF Chat	A de Bruijn-Erdős theorem for 1–2 metric spaces	2014	Vašek Chvátal
+	Untersuchungen über allgemeine Metrik	2002	Karl Menger
+	On a combinatorial problem	1948	FA Dick de Bruijn P. Erdős
+	Introduction to Geometry	1962	T H O‘Beirne
+	Introduction to Geometry.	1961	G. M. Petersen H. S. M. Coxeter