A new class of graphs that satisfies the Chen-Chvátal conjecture

DOI10.1002/JGT.22142MaRDI QIDQ4604017zbMATH OpenOpenAlexWikidataFDO

Authors Pierre Aboulker, Martin Matamala, Paul Rochet, José Zamora

Publication date 23 February 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06011

zbMATH Keywords

graph metricChen-Chvátal conjecture

Mathematics Subject Classification ID

Distance in graphs (05C12)

Abstract: A well-known combinatorial theorem says that a set of n non-collinear points in the plane determines at least n distinct lines. Chen and Chv'atal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work we prove a slightly stronger version of Chen and Chv'atal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.

Recommendations

• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
• A de Bruijn-Erdős theorem for chordal graphs
• Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
• Solution of the Chen-Chvátal conjecture for specific classes of metric spaces
• A de Bruijn-Erdős theorem and metric spaces

Cites work

• A De Bruijn-Erdős theorem for \(1\)-\(2\) metric spaces.
• A de Bruijn-Erdős theorem and metric spaces
• A de Bruijn-Erdős theorem for chordal graphs
• Graph Classes: A Survey
• Graph metric with no proper inclusion between lines
• Lines in hypergraphs
• Lines, betweenness and metric spaces
• Number of lines in hypergraphs
• On rigid circuit graphs
• Problems related to a de Bruijn-Erdös theorem
• Sylvester-Gallai theorem and metric betweenness
• 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

(12)

• A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs
• A de Bruijn-Erdős theorem in graphs?
• Solution of the Chen-Chvátal conjecture for specific classes of metric spaces
• Bisplit graphs satisfy the Chen-Chvátal conjecture
• scientific article; zbMATH DE number 2042724 (Why is no real title available?)
• Universal lines in graphs
• Lines in bipartite graphs and in 2‐metric spaces
• Chen and Chvátal's conjecture in tournaments
• Chen-Chvátal’s conjecture for graphs with restricted girth
• Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
• Lines in the plane with the \(L_1\) metric

This page was built for publication: A new class of graphs that satisfies the Chen-Chvátal conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604017)