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.

IdiomaEnglish
Páginas77-88
Número de páginas12
PublicaciónJournal of Graph Theory
Volumen87
Número de edición1
DOI
EstadoPublished - 1 ene 2018

Huella dactilar

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

Keywords

    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

    T2 - Journal of Graph Theory

    JF - Journal of Graph Theory

    SN - 0364-9024

    IS - 1

    ER -