Laurent Beaudou ; Giacomo Kahn ; Matthieu Rosenfeld
-
Bisplit graphs satisfy the Chen-Chvátal conjecture
dmtcs:4813 -
Discrete Mathematics & Theoretical Computer Science,
May 29, 2019,
vol. 21 no. 1, ICGT 2018
-
https://doi.org/10.23638/DMTCS-21-1-5Bisplit graphs satisfy the Chen-Chvátal conjectureArticle
Authors: Laurent Beaudou ; Giacomo Kahn ; Matthieu Rosenfeld
NULL##NULL##NULL
Laurent Beaudou;Giacomo Kahn;Matthieu Rosenfeld
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.
Volume: vol. 21 no. 1, ICGT 2018
Published on: May 29, 2019
Accepted on: April 22, 2019
Submitted on: September 10, 2018
Keywords: Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Funding:
Source : OpenAIRE Graph- Metric graph theory; Funder: French National Research Agency (ANR); Code: ANR-17-CE40-0015
- Enumeration on Graphs and Hypergraphs: Algorithms and Complexity; Funder: French National Research Agency (ANR); Code: ANR-15-CE40-0009