scientific article; zbMATH DE number 3258857

From MaRDI portal
Publication:5544082





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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5544082)