Regular graphs with prescribed chromatic number
Louis Caccetta, Norman J. Pullman · Journal of Graph Theory · 1990
Abstract We determine the minimum number of edges in a regular connected graph on n vertices, containing a complete subgraph of order k ≤ n/2. This enables us to confirm and strengthen a conjecture of P. Erdös on the existence of regular graphs with prescribed chromatic number.