10.23638/DMTCS-21-1-5
Beaudou, Laurent
Laurent
Beaudou
Kahn, Giacomo
Giacomo
Kahn
Rosenfeld, Matthieu
Matthieu
Rosenfeld
Bisplit graphs satisfy the Chen-Chv\'atal conjecture
episciences.org
2019
Computer Science - Discrete Mathematics
Mathematics - Combinatorics
contact@episciences.org
episciences.org
2018-09-10T11:22:06+02:00
2020-12-03T16:29:50+01:00
2019-05-29
eng
Journal article
https://dmtcs.episciences.org/4813
arXiv:1808.08710
1365-8050
PDF
1
Discrete Mathematics & Theoretical Computer Science ; vol. 21 no. 1, ICGT 2018 ; 1365-8050
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.