|
|||||
|
|
On Turán’s theorem for sparse graphs |
|
| Authors: | M. Ajtai P. Erdős J. Komlós E. Szemerédi |
| Affiliation: | (1) Mathematical Institute of the Hungarian Academy of Sciences, H-1053 Budapest, Hungary |
| Abstract: | For a graphG withn vertices and average valencyt, Turán’s theorem yields the inequalityα≧n/(t+1) whereα denotes the maximum size of an independent set inG. We improve this bound for graphs containing no large cliques. |
| Keywords: | 05 C 35 05 C 55 |
| 本文献已被 SpringerLink 等数据库收录！ | |