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

Pierre Aboulker, Laurent Beaudou, Martı́n Matamala, José Zamora

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

Resumen

A set of (Formula presented.) points in the plane which are not all collinear defines at least (Formula presented.) 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.

Idioma originalInglés
PublicaciónJournal of Graph Theory
DOI
EstadoEn prensa - 2022

Áreas temáticas de ASJC Scopus

  • Geometría y topología
  • Matemáticas discretas y combinatorias

Huella

Profundice en los temas de investigación de 'Graphs with no induced house nor induced hole have the de Bruijn–Erdös property'. En conjunto forman una huella única.

Citar esto