A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture
Pierre Aboulker, Martı́n Matamala, Paul Rochet, José Zamora · Journal of Graph Theory · 2017
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.