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

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, Béla Bollobas, and Susan Tucker,*The independence ratio and maximum degree of a graph*, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., 1976, pp. 43–50. Congressus Numerantium, No. XVII. MR**0437374****[2]**R. L. Brooks,*On colouring the nodes of a network*, Proc. Cambridge Philos. Soc.**37**(1941), 194–197. MR**0012236****[3]**S. Fajtlowicz,*The independence ratio for cubic graphs*, Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Utilitas Math., Winnipeg, Man., 1977, pp. 273–277. Congressus Numerantium, No. XIX. MR**0491297****[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