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

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

Resultado de la investigación: Article

Resumen

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.

Idioma originalEnglish
Páginas (desde-hasta)77-88
Número de páginas12
PublicaciónJournal of Graph Theory
Volumen87
N.º1
DOI
EstadoPublished - 1 ene 2018

Huella dactilar

Distance-hereditary Graphs
Chordal Graphs
Line
Graph in graph theory
Theorem
Metric space
Distinct
Class
Family

ASJC Scopus subject areas

  • Geometry and Topology

Citar esto

Aboulker, P. ; Matamala, M. ; Rochet, P. ; Zamora, J. / A New Class of Graphs That Satisfies the Chen-Chvátal Conjecture. En: Journal of Graph Theory. 2018 ; Vol. 87, N.º 1. pp. 77-88.
@article{e3619f39baab499d973010c8f1ee1155,
title = "A New Class of Graphs That Satisfies the Chen-Chv{\'a}tal Conjecture",
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{\'a}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{\'a}tal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.",
keywords = "Chen-Chvatal conjecture, graphe metric",
author = "P. Aboulker and M. Matamala and P. Rochet and J. Zamora",
year = "2018",
month = "1",
day = "1",
doi = "10.1002/jgt.22142",
language = "English",
volume = "87",
pages = "77--88",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "1",

}

A New Class of Graphs That Satisfies the Chen-Chvátal Conjecture. / Aboulker, P.; Matamala, M.; Rochet, P.; Zamora, J.

En: Journal of Graph Theory, Vol. 87, N.º 1, 01.01.2018, p. 77-88.

Resultado de la investigación: Article

TY - JOUR

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

AU - Aboulker, P.

AU - Matamala, M.

AU - Rochet, P.

AU - Zamora, J.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Chen-Chvatal conjecture

KW - graphe metric

UR - http://www.scopus.com/inward/record.url?scp=85015254868&partnerID=8YFLogxK

U2 - 10.1002/jgt.22142

DO - 10.1002/jgt.22142

M3 - Article

VL - 87

SP - 77

EP - 88

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -