A GENERALIZATION OF A RESULT OF DIRAC

Abstract

Let $G$ be a graph, $\chi(G)=r$ and $cl(G) < r$. Dirac has proved in [2] that for such graph $|V(G)|\ge r+2$ and $|V(G)| = r+2$ only if $G=K_{r-3}+C_5$. The main result in the current article generalizes the proposition mentioned above (Theorem 2.1). As a consequence of Theorem 2.1, some results for Folkman graphs are obtained (Theorems 7.1--7.4, 8.1).