Logo image
Sign in
Bisplit graphs satisfy the Chen-Chvátal conjecture
Journal article   Peer reviewed

Bisplit graphs satisfy the Chen-Chvátal conjecture

Laurent Beaudou, Giacomo Kahn and Matthieu Rosenfeld
Discrete Mathematics and Theoretical Computer Science, Vol.21(1)
29/05/2019

Abstract

Computer Science - Discrete Mathematics Mathematics - Combinatorics
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.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image