Maximum diameter of 3‐ and 4‐colorable graphs

Erdős et al. made conjectures for the maximum diameter of connected graphs without a complete subgraphK k + 1${K}_{k+1}$ , which have ordern $n$ and minimum degreeδ $\delta $ . Settling a weaker version of a problem, by strengthening theK k + 1${K}_{k+1}$ ‐free condition tok $k$ ‐colorable, we solve the problem fork = 3 $k=3$ andk = 4 $k=4$ using a unified linear programming duality approach. The casek = 4 $k=4$ is a substantial simplification of the result of Czabarka et al.