PreprintCC BY-NC-ND 4.0arXiv
Counterexamples to two conjectures on the diameter of clique-free graphs
Abstract
Erdős et al. (JCT-B, 1989) conjectured that, for integers r≥ 2 and δ≥ 2 with 3r−1|δ, every connected K2r+1-free graph of order n and minimum degree δ has diameter at most $ \frac{3r-1}{r}\cdot \frac{n}δ+O(1)$. Czabarka et al. (JCT-B, 2021) later proposed the following generalization: for every k≥ 3 and δ≥⌈3k/2⌉−1, every connected Kk+1-free graph of order n and minimum degree at least δ has diameter at most (3−2/k)·n/δ+O(1). We disprove the latter conjecture, including its k-colorable version, for every k≥ 7 and sufficiently large δ. When k=2r≥ 8 and 3r−1|δ, our construction also disproves the conjecture of Erdős et al. (JCT-B, 1989).
Related
- The 𝒜α-Spectral Turán Problem for s-Clique Tensors of Kr+1-Free Graphs
- Minimum orders of clique oddomorphism counterexamples
- Counterexamples to Two Conjectures on Tangles in Matroid Minors
- Non-freezing of the proximity digraph and non-pseudostable convergence in heterogeneous Hegselmann--Krause models: Counterexamples to conjectures and results of Mirtabatabaei and Bullo
- A simple construction of smooth counterexamples to the Loewner and Carathéodory conjectures
BibTeX
@misc{chen2026counterexamples,
title = {{Counterexamples to two conjectures on the diameter of clique-free graphs}},
author = {Hangdi Chen and Yaojun Chen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03346},
eprint = {2609.03346},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03346},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Counterexamples to two conjectures on the diameter of clique-free graphs
AU - Hangdi Chen
AU - Yaojun Chen
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03346
UR - https://arxiv.org/abs/2609.03346
AB - Erdős et al. (JCT-B, 1989) conjectured that, for integers r≥ 2 and δ≥ 2 with 3r−1|δ, every connected K_2r+1-free graph of order n and minimum degree δ has diameter at most $ \frac{3r-1}{r}\cdot \frac{n}δ+O(1)$. Czabarka et al. (JCT-B, 2021) later proposed the following generalization: for every k≥ 3 and δ≥⌈3k/2⌉−1, every connected K_k+1-free graph of order n and minimum degree at least δ has diameter at most (3−2/k)·n/δ+O(1). We disprove the latter conjecture, including its k-colorable version, for every k≥ 7 and sufficiently large δ. When k=2r≥ 8 and 3r−1|δ, our construction also disproves the conjecture of Erdős et al. (JCT-B, 1989).
ER -