Diameter of 4-colourable graphs

We prove that for every connected 4-colourable graph GG of order nn and minimum degree δ≥1δ≥1, diam(G)≤5n2δ−1. This is a first step toward proving a conjecture of Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 279–285] from 1989. Our bound is tight since a family of graphs constructed in the above-cited reference has diameter 5n2δ−5.