2025/02/12 by Stijn Cambie, Jorik Jooken, Cambie, Stijn +1 · 2 citations
Mathematics · #Advanced Algebra and Geometry #Algebraic Geometry and Number Theory #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2502.08626
We consider the Erdős, Pach, Pollack and Tuza problem, asking for the maximum diameter of a graph with given order n, minimum degree δ and clique number at most ω. We solve their problem asymptotically for the first hard case, ω≤ 3, for the smallest values of δ by determining the smallest rational number f(δ) such that diam(G) ≤ f(δ)n+O(1) for all graphs G with order n, minimum degree δ and clique number ω≤ 3. We also consider the weaker version where the clique number ω≤ 3 is replaced by having chromatic number χ≤ 3 and solve this version for small δ, thereby yielding a counterexample to a conjecture of Erdős et al. in a regime where this conjecture was still open. When restricting the conjecture to graphs with chromatic number χ≤ 3, we show that this counterexample appears for the smallest possible δ, namely δ=16.