Bisplit graphs satisfy the Chen-Chvátal conjecture

zbMATH Open1417.05043arXiv1808.08710MaRDI QIDQ5226828FDOQ5226828

Authors: Laurent Beaudou, Giacomo Kahn, Matthieu Rosenfeld 

Publication date: 1 August 2019

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1808.08710

Recommendations

• A new class of graphs that satisfies the Chen-Chvátal conjecture
• Solution of the Chen-Chvátal conjecture for specific classes of metric spaces
• Bisplit graphs
• The Erdős-Lovász tihany conjecture for quasi-line graphs
• Split graphs: combinatorial species and asymptotics

zbMATH Keywords

distancesbisplit graphsChen-Chvátal conjecture

Mathematics Subject Classification ID

Distance in graphs (05C12)

Cited In (4)

• Counting vertices and cubes in median graphs of circular split systems
• Solution of the Chen-Chvátal conjecture for specific classes of metric spaces
• Lines in bipartite graphs and in 2‐metric spaces
• Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs

This page was built for publication: Bisplit graphs satisfy the Chen-Chvátal conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226828)