Bisplit graphs satisfy the Chen-Chvátal conjecture

zbMATHMaRDI QIDQ5226828FDO

Authors Laurent Beaudou, Giacomo Kahn, Matthieu Rosenfeld

Publication date 1 August 2019

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

zbMATH Keywords

distancesbisplit graphsChen-Chvátal conjecture

Mathematics Subject Classification ID

Distance in graphs (05C12)

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.

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

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)