Some Ramsey-type numbers and the independence ratio

Author:
William Staton

Journal:
Trans. Amer. Math. Soc. **256** (1979), 353-370

MSC:
Primary 05C55

DOI:
https://doi.org/10.1090/S0002-9947-1979-0546922-6

MathSciNet review:
546922

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: If each of *k, m*, and *n* is a positive integer, there is a smallest positive integer with the property that each graph *G* with at least *r* vertices, and with maximum degree not exceeding *k*, has either a complete subgraph with *m* vertices, or an independent subgraph with *n* vertices. In this paper we determine , for all *n*. As a corollary we obtain the largest possible lower bound for the independence ratio of graphs with maximum degree three containing no triangles.

**[1]**Michael Albertson, Bela Bollobas and Susan Tucker,*The independence ratio and maximum degree of a graph*, Proc. 7th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, LSU, 1976, pp. 43-50. MR**0437374 (55:10305)****[2]**R. L. Brooks,*On colouring the nodes of a network*, Proc. Cambridge Philos. Soc.**37**(1941), 194-197. MR**0012236 (6:281b)****[3]**S. Fajtlowicz,*The independence ratio for cubic graphs*, Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, LSU, 1977, pp. 273-277. MR**0491297 (58:10560)****[4]**F. P. Ramsey,*On a problem of formal logic*, Proc. London Math. Soc.**30**(1930), 264-286.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
05C55

Retrieve articles in all journals with MSC: 05C55

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1979-0546922-6

Keywords:
Independence,
cubic graphs

Article copyright:
© Copyright 1979
American Mathematical Society