Bisplit graphs satisfy the Chen-Chvátal conjecture

Beaudou, Laurent; Kahn, Giacomo; Rosenfeld, Matthieu

Request a copy

Article (Scientific journals)

Bisplit graphs satisfy the Chen-Chvátal conjecture

Beaudou, Laurent; Kahn, Giacomo; Rosenfeld, Matthieu

2019 • In Discrete Mathematics and Theoretical Computer Science, 21 (1), p. 5509

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/248941

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Beaudou_Bisplit-graphs_2020.pdf

Publisher postprint (175.45 kB)

Request a copy

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Bisplit graphs; Chen-Chvátal conjecture; Distances; Complete bipartite graphs; Metric spaces; Stable sets; Universal lines; Vertex set; Graph theory

Abstract :

[en] In this paper, we give a lengthy proof of a small result! A graph is bisplit if its vertex set can be partitioned into three stable sets with two of them inducing a complete bipartite graph. We prove that these graphs satisfy the Chen-Chv atal conjecture: their metric space (in the usual sense) has a universal line (in an unusual sense) or at least as many lines as the number of vertices. © 2019 by the author(s).

Disciplines :

Mathematics

Author, co-author :

Beaudou, Laurent; Higher School of Economics, Moscow, Russian Federation

Kahn, Giacomo; Université D'Orléans, France

Rosenfeld, Matthieu ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Bisplit graphs satisfy the Chen-Chvátal conjecture

Publication date :

2019

Journal title :

Discrete Mathematics and Theoretical Computer Science

ISSN :

1365-8050

eISSN :

1462-7264

Publisher :

Maison de l'informatique et des mathematiques discretes, France

Volume :

Issue :

Pages :

5509

Peer reviewed :

Peer Reviewed verified by ORBi

Name of the research project :

ANR-15-CE40-0009: 2015-2018

Funders :

AAP - Association of Academic Physiatrists [US-OH] [US-OH]
FEDER - Federación Española de Enfermedades Raras [ES]

Available on ORBi :

since 27 June 2020

Statistics

Number of views

41 (2 by ULiège)

Number of downloads

2 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

P. Aboulker, X. Chen, G. Huzhang, R. Kapadia, and C. Supko. Lines, betweenness and metric spaces. Discrete & Computational Geometry, 56:427-448, 2016.
P. Aboulker,M.Matamala, P. Rochet, and J. Zamora. A new class of graphs that satisfies the chen-chvátal conjectur. Journal of Graph Theory, 87:77-88, 2018.
L. Beaudou, A. Bondy, X. Chen, E. Chiniforooshan, M. Chudnovsky, V. Chvátal, N. Fraiman, and Y. Zwols. A de bruijn-erdös theorem for chordal graphs. The Electronic Journal of Combinatorics, 22(1), 2015. P70.
X. Chen and V. Chvátal. Problems related to a de bruijn-Erdös theorem. Discrete Applied Mathematics, 156:2101-2108, 2008.
V. Chvátal. A De Bruijn-Erdös Theorem in Graphs?, pages 149-176. Springer International Publishing, Cham, 2018. ISBN 978-3-319-97686-0. doi: 10.1007/978-3-319-97686-0 13. URL https://doi.org/10.1007/978-3-319-97686-0-13.
V. Chvátal. A de bruijn-erdös theorem for 1-2 metric spaces. Czechoslovak Mathematical Journal, 64(1): 45-51, Mars 2014.
N. G. de Bruijn and P. Erdös. On a combinatorial problem. In Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, 1948.
P. Erdös. Personal reminiscences and remarks on the mathematical work of tibor gallai. Combinatorica, 2(3):207-212, 1982.
J. J. Sylvester. Mathematical question 11851. The Educational Times, 46(383):156,Mars 1893.