Maximum diameter of 3-and 4-colorable graphs

Erdos et al. made conjectures for the maximum diameter of connected graphs without a complete subgraph Kk + 1 ${K}_{k+1}$, which have order n $n$ and minimum degree delta $\delta $. Settling a weaker version of a problem, by strengthening the Kk + 1 ${K}_{k+1}$-free condition to k $k$-colorable, we solve the problem for k = 3 $k=3$ and k = 4 $k=4$ using a unified linear programming duality approach. The case k = 4 $k=4$ is a substantial simplification of the result of Czabarka et al.