Geodesic
Bisplit graphs satisfy the Chen-Chv\'atal conjecture
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_1_a9,
     author = {Beaudou, Laurent and Kahn, Giacomo and Rosenfeld, Matthieu},
     title = {Bisplit graphs satisfy the {Chen-Chv\'atal} conjecture},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2019},
     doi = {10.23638/DMTCS-21-1-5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-5/}
}
TY  - JOUR
AU  - Beaudou, Laurent
AU  - Kahn, Giacomo
AU  - Rosenfeld, Matthieu
TI  - Bisplit graphs satisfy the Chen-Chv\'atal conjecture
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-5/
DO  - 10.23638/DMTCS-21-1-5
LA  - en
ID  - DMTCS_2019_21_1_a9
ER  - 
%0 Journal Article
%A Beaudou, Laurent
%A Kahn, Giacomo
%A Rosenfeld, Matthieu
%T Bisplit graphs satisfy the Chen-Chv\'atal conjecture
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-5/
%R 10.23638/DMTCS-21-1-5
%G en
%F DMTCS_2019_21_1_a9
Beaudou, Laurent; Kahn, Giacomo; Rosenfeld, Matthieu. Bisplit graphs satisfy the Chen-Chv\'atal conjecture. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi: 10.23638/DMTCS-21-1-5

Cité par Sources :