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, 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.

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

American Mathematical Society