Browsing by Author "Staton, William Alfred"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Some ramsey-type numbers and the independence ratio
    (1978) Staton, William Alfred; Bourgin, David G.; Etgen, Garrett J.; Hausen, Jutta; Walker, Philip; Yoes, M. G., Jr.
    If each of k, m, and n is a positive integer, there is a smallest positive integer r = r[lowered k](m,n) 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, r[lowered 3](3,n) = 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.