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)



The independence ratio and genus of a graph

Authors: Michael O. Albertson and Joan P. Hutchinson
Journal: Trans. Amer. Math. Soc. 226 (1977), 161-173
MSC: Primary 05C10
MathSciNet review: 0437372
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we study the relationship between the genus of a graph and the ratio of the independence number to the number of vertices.

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

  • [1] M. O. Albertson, Finding an independent set in a planar graph, Graphs and Combinatorics (Proc. Capital Conf. on Graph Theory and Combinatorics, George Washington Univ., Washington, D.C., 1973), Lecture Notes in Math., vol. 406 (R. Bari and F. Harary, editors), Springer-Verlag, Berlin and New York, 1974, pp. 173-179. MR 51 #5359. MR 0369123 (51:5359)
  • [2] -, A lower bound for the independence number of a planar graph, J. Combinatorial Theory (B) 20 (1976), 84-93. MR 0424599 (54:12558)
  • [3] M. O. Albertson and J. P. Hutchinson, On the independence ratio of a graph, J. Graph Theory (submitted).
  • [4] -, The maximum size of an independent set in a nonplanar graph, Bull. Amer. Math. Soc. 81 (1975), 554-555. MR 51 #267. MR 0364012 (51:267)
  • [5] -, The maximum size of an independent set in a toroidal graph, Proc. Sixth Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg, 1975, pp. 35-46. MR 0392636 (52:13453)
  • [6] C. Berge, Graphs and hypergraphs, North-Holland, Amsterdam, 1973. MR 50 #9640. MR 0357172 (50:9640)
  • [7] G. A. Dirac, Short proof of a map-color theorem, Canad. J. Math. 9 (1957), 225-226. MR 19, 161. MR 0086306 (19:161c)
  • [8] P. Edelman, Independence ratios of graphs that ended on $ {S_n}$, Ars Combinatoria (to appear).
  • [9] J. Mayer, Inégalités nouvelles dans le problème des quatre couleurs, J. Combinatorial Theory (B) 19 (1975), 119-149. MR 0432486 (55:5474)
  • [10] G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438-445. MR 37 #3959. MR 0228378 (37:3959)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C10

Retrieve articles in all journals with MSC: 05C10

Additional Information

Keywords: Genus, independence number, noncontractible cycle
Article copyright: © Copyright 1977 American Mathematical Society

American Mathematical Society