Some ramsey-type numbers and the independence ratio

Date

1978

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.

Description

Keywords

Citation