Some ramsey-type numbers and the independence ratio
Date
1978
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
If each of k, m, and n is a positive integer, there is a smallest positive integer r = rlowered k with the property that each graph G with at least r vertices, and with maximum degree not exceeding k, has either a complete subset with m vertices, or an independent subset with n vertices. In this paper, rlowered 3 = r(n) is determined for all n. A corollary is the largest possible lower bound for the independence ratio in graphs with maximum degree three containing no triangles.