A note on the independence number of triangle-free graphs |
| |
Authors: | James B Shearer |
| |
Institution: | Department of Mathematics, University of California, Berkeley, CA 94720, USA |
| |
Abstract: | Let G be a triangle-free graph on n points with average degree d. Let α be the independence number of G. In this note we give a simple proof that α ? n (d ln d ? d + 1)/(d ? 1)2. We also consider what happens when G contains a limited number of triangles. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|