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

DOI10.1002/JGT.22142zbMATH Open1380.05043arXiv1606.06011OpenAlexW2963002687WikidataQ122919391 ScholiaQ122919391MaRDI QIDQ4604017FDOQ4604017

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)

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.

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

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

zbMATH Keywords

graph metricChen-Chvátal conjecture

Mathematics Subject Classification ID

Distance in graphs (05C12)

Cites Work

• Graph Classes: A Survey
• On rigid circuit graphs
• Sylvester-Gallai theorem and metric betweenness
• Towards a de Bruijn-Erdős theorem in the \(L_1\)-metric
• A de Bruijn-Erdős theorem for chordal graphs
• Graph metric with no proper inclusion between lines
• Lines in hypergraphs
• Number of lines in hypergraphs
• A De Bruijn-Erdős theorem for \(1\)-\(2\) metric spaces.
• Lines, betweenness and metric spaces
• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
• A de Bruijn-Erdős theorem and metric spaces
• Problems related to a de Bruijn-Erdös theorem

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
• Universal lines in graphs
• Title not available (Why is that?)
• 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)