Some Ramsey-type numbers and the independence ratio

Staton, William

doi:10.1090/S0002-9947-1979-0546922-6

Some Ramsey-type numbers and the independence ratio
HTML articles powered by AMS MathViewer

by William Staton

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

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

PDF | Request permission

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

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) Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976, pp. 43–50. MR 0437374
R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197. MR 12236, DOI 10.1017/S030500410002168X
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), Congressus Numerantium, No. XIX, Utilitas Math., Winnipeg, Man., 1977, pp. 273–277. MR 0491297

On a problem of formal logic

30