The independence ratio of regular graphs

Bollobás, Béla

doi:10.1090/S0002-9939-1981-0624948-6

The independence ratio of regular graphs
HTML articles powered by AMS MathViewer

by Béla Bollobás PDF

Proc. Amer. Math. Soc. 83 (1981), 433-436 Request permission

Abstract:

As a special case of a general result, it is shown that there are cubic graphs of arbitrarily large girth with independence ratio less than $6/13$.

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
Michael O. Albertson and Joan P. Hutchinson, The maximum size of an independent set in a nonplanar graph, Bull. Amer. Math. Soc. 81 (1975), 554–555. MR 364012, DOI 10.1090/S0002-9904-1975-13735-9
Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
Béla Bollobás, Chromatic number, girth and maximal degree, Discrete Math. 24 (1978), no. 3, 311–314. MR 523321, DOI 10.1016/0012-365X(78)90102-4
Béla Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), no. 4, 311–316. MR 595929, DOI 10.1016/S0195-6698(80)80030-8
R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197. MR 12236
P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9
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
S. Fajtlowicz, On the size of independent sets in graphs, Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) Congress. Numer., XXI, Utilitas Math., Winnipeg, Man., 1978, pp. 269–274. MR 527955
Glenn Hopkins and William Staton, Girth and independence ratio, Canad. Math. Bull. 25 (1982), no. 2, 179–186. MR 663611, DOI 10.4153/CMB-1982-024-9
William Staton, Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc. 256 (1979), 353–370. MR 546922, DOI 10.1090/S0002-9947-1979-0546922-6