Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The independence ratio of regular graphs


Author: Béla Bollobás
Journal: Proc. Amer. Math. Soc. 83 (1981), 433-436
MSC: Primary 05C99; Secondary 05C15, 05C35
DOI: https://doi.org/10.1090/S0002-9939-1981-0624948-6
MathSciNet review: 624948
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] M. O. Albertson, B. Bollobás and S. Tucker, The independence ratio and maximum degree of a graph, Proc. Seventh South Eastern Conf. on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., 1976, pp. 43-50. MR 0437374 (55:10305)
  • [2] M. O. Albertson and J. P. Hutchinson, The maximum size of an independent set in a nonplanar graph, Bull. Amer. Math. Soc. 81 (1975), 554-555. MR 0364012 (51:267)
  • [3] B. Bollobás, Extremal graph theory, London Math. Soc. Monographs, No. 11, Academic Press, London and New York, 1978. MR 506522 (80a:05120)
  • [4] -, Chromatic number, girth and maximum degree, Discrete Math. 24 (1978), 311-314. MR 523321 (80e:05058)
  • [5] -, A probabilistic proof of an asymptotic formula for the number of regular graphs, European J. Combinatorics 1 (1980), 311-316. MR 595929 (82i:05045)
  • [6] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194-197. MR 0012236 (6:281b)
  • [7] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38. MR 0102081 (21:876)
  • [8] S. Fajtlowicz, The independence ratio for cubic graphs, Proc. Eighth South Eastern Conf. on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Utilitas Math., Winnipeg, Man., 1977, pp. 273-277. MR 0491297 (58:10560)
  • [9] -, On the size of independent sets in graphs, Proc. Ninth South Eastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Math., Winnipeg, Man., 1978, pp. 269-274. MR 527955 (80j:05089)
  • [10] G. W. Hopkins and W. Staton, Girth and independence ratio (to appear). MR 663611 (83j:05045)
  • [11] W. Staton, Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc. 256 (1979), 353-370. MR 546922 (81g:05083)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C99, 05C15, 05C35

Retrieve articles in all journals with MSC: 05C99, 05C15, 05C35


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1981-0624948-6
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society