Home
A generalization of a result of Dirac
Author: N. Nenov
Let $G$ be a graph, $\chi(G)=r$ and $\cll(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).
Annotation in PDF format:
(PDF document
32Kb)
(PDF document
32Kb)
Keywords: hromatic number, Folkman graph, fi-critical graph
2000 MSC:
05C15,
05C55
