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

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

doi:10.1002/jgt.22142

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

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

Facultad Ciencias Exactas

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

10 Citas (Scopus)

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 original	Inglés
Páginas (desde-hasta)	77-88
Número de páginas	12
Publicación	Journal of Graph Theory
Volumen	87
N.º	1
DOI	https://doi.org/10.1002/jgt.22142
Estado	Publicada - ene. 2018

Áreas temáticas de ASJC Scopus

Geometría y topología

Acceder al documento

10.1002/jgt.22142

Otros archivos y enlaces

Enlace a la publicación en Scopus

Citar esto

@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",

note = "Funding Information: ∗Contract grant sponsor: Fondecyt Regular 1160975; contract grant sponsor: Mile-nio Informaci{\'o}n y Coordinaci{\'o}n en Redes ICM/FIC RC130003.",

year = "2018",

month = jan,

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",

}

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.

N1 - Funding Information: ∗Contract grant sponsor: Fondecyt Regular 1160975; contract grant sponsor: Mile-nio Información y Coordinación en Redes ICM/FIC RC130003.

PY - 2018/1

Y1 - 2018/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

AN - SCOPUS:85015254868

SN - 0364-9024

VL - 87

SP - 77

EP - 88

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

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

Resumen

Áreas temáticas de ASJC Scopus

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto