Bisplit graphs satisfy the Chen-Chvátal conjecture

08/27/2018
by   Laurent Beaudou, et al.
0

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átal 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset