Premium
A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture
Author(s) -
Aboulker P.,
Matamala M.,
Rochet P.,
Zamora J.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22142
Subject(s) - mathematics , combinatorics , conjecture , chordal graph , chen , plane (geometry) , discrete mathematics , class (philosophy) , graph , computer science , paleontology , geometry , artificial intelligence , biology
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.