Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

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 $ r\, = \,{r_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 subgraph with m vertices, or an independent subgraph with n vertices. In this paper we determine $ {r_3}(3,\,n)\, = \,r(n)$, 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.


References [Enhancements On Off] (What's this?)

  • [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.

Similar Articles

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