A New Class of Graphs That Satisfies the Chen-Chvátal Conjecture

P. Aboulker, M. Matamala, P. Rochet, J. Zamora

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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átal 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átal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.

Original languageEnglish
Pages (from-to)77-88
Number of pages12
JournalJournal of Graph Theory
Volume87
Issue number1
DOIs
Publication statusPublished - Jan 2018

Keywords

  • Chen-Chvatal conjecture
  • graphe metric

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'A New Class of Graphs That Satisfies the Chen-Chvátal Conjecture'. Together they form a unique fingerprint.

Cite this