2020/09/05 by Czabarka, Éva, Singgih, Inne, Székely, László A.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2009.02611
Erdős, Pach, Pollack and Tuza [J. Combin. Theory, B 47, (1989), 279-285] conjectured that the diameter of a K2r-free connected graph of order n and minimum degree δ≥ 2 is at most (2(r-1)(3r+2))/((2r2-1))⋅ \fracnδ + O(1) for every r≥ 2, if δ is a multiple of (r-1)(3r+2). For every r>1 and δ≥ 2(r-1), we create K2r-free graphs with minimum degree δ and diameter ((6r-5)n)/((2r-1)δ+2r-3)+O(1), which are counterexamples to the conjecture for every r>1 and δ>2(r-1)(3r+2)(2r-3). The rest of the paper proves positive results under a stronger hypothesis, k-colorability, instead of being Kk+1-free. We show that the diameter of connected k-colorable graphs with minimum degree ≥ δ and order n is at most (3-(1)/(k-1))\fracnδ+O(1), while for k=3, it is at most (57n)/(23δ)+O(1).