On the maximum diameter of \(k\)-colorable graphs (Q820842)

The authors consider the problem of the maximum diameter of a connected graph \(G\) with order \(n\), minimum degree \(\delta\) and chromatic number at most \(k.\) This problem is a variant with the chromatic number as an extra constraint for an older problem which dates back to e.g. [\textit{J. W. Moon}, Mich. Math. J. 12, 349--351 (1965; Zbl 0134.19603)]. In this paper, they prove that for every \(k \ge 3\), \(\left(3-\frac{1}{k-1}\right)\frac n {\delta}-1\) is an upperbound for the diameter of such a graph \(G\). First, the authors prove some properties of graphs that attain the maximum possible diameter. For this, they introduce and investigate clump graphs. These clump graphs are formed for a fixed coloring by considering colour classes of layers (set of vertices at distance \(i\) from a fixed vertex), called clumps. Next, they use a linear programming duality approach to reduce the problem to a packing problem. For \(k=3\), more work is done to improve the result to \(\frac{57}{23}\frac n {\delta}+O_{\delta}(1).\) Additional linear constraints are obtained in this case using the principle of exclusion-inclusion.