No label defined (Q5544082)

We quote the authors. ''In a graph-theoretic colloquium at Smolenice, \textit{G. A. Dirac} conjectured (see ibid. p. 167 problem 5) that the chromatic number of a proper regular subgraph of a complete \(n\)-gon is \(\leq 3n/5\). We shall prove this conjecture. In fact we shall prove the following theorem (\(G^{(n)}\) always denotes a graph with \(n\) vertices). Theorem. Let \(G^{(n)}\) be a regular graph of valence \(r<n-1\) and chromatic number \(k\). Then \(k \leq 3n/5\), with equality if and only if the components of the complementary graph \(\overline{G^{(n)}}\) of \(G^{(n)}\) are pentagons.''