Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
From MaRDI portal
Publication:6081879
Other designs, configurations (05B30) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Other finite incidence structures (geometric aspects) (51E30) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)
Abstract: A set of n points in the plane which are not all collinear defines at least n distinct lines. Chen and Chv'atal 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.
Recommendations
- Erdős–Hajnal for graphs with no 5‐hole
- Graphs with the Erdős-Ko-Rado property
- Graphs with no induced \(K_{2,t}\)
- Almost all H-free graphs have the Erdős-Hajnal property
- The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
- Graphs with no induced wheel and no induced antiwheel
- Towards Erdős-Hajnal for graphs with no 5-hole
- A de Bruijn-Erdős theorem in graphs?
- Even-hole-free graphs. I: Decomposition theorem
- Graphs with induced-saturation number zero
Cites work
- A de Bruijn-Erdős theorem and metric spaces
- A De Bruijn-Erdős theorem for 1-2 metric spaces.
- A de Bruijn-Erdős theorem for chordal graphs
- A de Bruijn-Erdős theorem in graphs?
- A new class of graphs that satisfies the Chen-Chvátal conjecture
- Lines in bipartite graphs and in 2‐metric spaces
- Lines, betweenness and metric spaces
- Personal reminiscences and remarks on the mathematical work of Tibor Gallai
- Problems related to a de Bruijn-Erdös theorem
- The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
- Towards a de Bruijn-Erdős theorem in the \(L_1\)-metric
Cited in
(10)- A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs
- A de Bruijn-Erdős theorem for chordal graphs
- Graph metric with no proper inclusion between lines
- The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
- A new class of graphs that satisfies the Chen-Chvátal conjecture
- A de Bruijn-Erdős theorem and metric spaces
- Chen-Chvátal’s conjecture for graphs with restricted girth
- Lines on digraphs of low diameter
- Quasimetric spaces with few lines
- Lower general position sets in graphs
This page was built for publication: Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081879)
