Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza
type: Item
instance of: scholarly article
title: Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza
zbMATH Open document ID: 1479.05168
author: Éva Czabarka
author: Inne Singgih
author: László A. Székely
published in: Journal of Combinatorial Theory. Series B
publication date: 2021-09-16T00:00:00Z
review text: \textit{P. Erdős} et al. [ibid. 47, No. 1, 73--79 (1989; Zbl 0686.05029)] conjectured that the diameter of a \(K_{2r}\)-free connected graph of order \(n\) and minimum degree \(\delta\geq 2\) is at most \(\frac{2n(r-1)(3r+2)}{(2r^2-1)\delta}+O(1)\) for every \(r\geq 2\) where \(\delta\) is a multiple of \((r-1)(3r+2)\). In this paper, as counterexamples to the above conjecture, a class of \(K_{2r}\)-free graphs are constructed with minimum degree \(\delta\) and diameter \(\frac{(6r-5)n}{(2r-1)\delta+2r-3}+O(1)\) for \(r>1\) and \(\delta>2(r-1)(3r+2)(2r-3)\).
reviewed by: Kexiang Xu
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 7396129
zbMATH Keywords: diameter
zbMATH Keywords: minimum degree
MaRDI profile type: Publication
full work available at URL: j.jctb.2021.06.001
OpenAlex ID: W3169215024
cites work: Ordre Minimum D'un Graphe Simple De Diametre, Degre Minimum Et Connexite Donnes
cites work: Graphs of maximum diameter
cites work: Diameter of 4-colourable graphs
cites work: Q4382659
cites work: Q3946193
cites work: On the diameter of a graph
DOI: 10.1016/J.JCTB.2021.06.001
description: scientific article; zbMATH DE number 7396129