Graphs with no induced house nor induced hole have the de Bruijn–Erdös property - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Journal of Graph Theory Année : 2022

Graphs with no induced house nor induced hole have the de Bruijn–Erdös property

Résumé

A set of n points in the plane which are not all collinear defines at least n distinct lines. Chen and Chvátal conjectured in 2008 that a similar result can be achieved in the broader context of finite metric spaces. This conjecture remains open even for graph metrics. In this article we prove that graphs with no induced house nor induced cycle of length at least 5 verify the desired property. We focus on lines generated by vertices at distance at most 2, define a new notion of 'good pairs' that might have application in larger families, and finally use a discharging technique to count lines in irreducible graphs.
Fichier non déposé

Dates et versions

hal-03559740 , version 1 (07-02-2022)

Identifiants

Citer

Pierre Aboulker, Laurent Beaudou, Martín Matamala, José Zamora. Graphs with no induced house nor induced hole have the de Bruijn–Erdös property. Journal of Graph Theory, 2022, ⟨10.1002/jgt.22799⟩. ⟨hal-03559740⟩
42 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More