  P. Erd\H{o}s, J. Pach, R. Pollack, and Z. Tuza [J. Combin. Theory, B 47
(1989), 279--285] made conjectures for the maximum diameter of connected graphs
without a complete subgraph $K_{k+1}$, which have order $n$ and minimum degree
$\delta$. Settling a weaker version of a problem, by strengthening the
$K_{k+1}$-free condition to $k$-colorable, we solve the problem for $k=3$ and
$k=4$ using a unified linear programming duality approach. The case $k=4$ is a
substantial simplification of the result of \'E. Czabarka, P. Dankelmann, and
L. A. Sz\'ekely [Europ. J. Comb., 30 (2009), 1082--1089].
