The independence ratio and genus of a graph
HTML articles powered by AMS MathViewer
- by Michael O. Albertson and Joan P. Hutchinson PDF
- Trans. Amer. Math. Soc. 226 (1977), 161-173 Request permission
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
- Michael O. Albertson, Finding an independent set in a planar graph, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973) Lecture Notes in Math., Vol. 406, Springer, Berlin, 1974, pp. 173–179. MR 0369123
- Michael O. Albertson, A lower bound for the independence number of a planar graph, J. Combinatorial Theory Ser. B 20 (1976), no. 1, 84–93. MR 424599, DOI 10.1016/0095-8956(76)90071-x M. O. Albertson and J. P. Hutchinson, On the independence ratio of a graph, J. Graph Theory (submitted).
- 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
- Michael O. Albertson and Joan P. Hutchinson, The maximum size of an independent set in a toroidal graph, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975, pp. 35–46. MR 0392636
- Claude Berge, Graphs and hypergraphs, North-Holland Mathematical Library, Vol. 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka. MR 0357172
- G. A. Dirac, Short proof of a map-colour theorem, Canadian J. Math. 9 (1957), 225. MR 86306, DOI 10.4153/CJM-1957-027-2 P. Edelman, Independence ratios of graphs that ended on ${S_n}$, Ars Combinatoria (to appear).
- Jean Mayer, Inégalités nouvelles dans le problème des quatre couleurs, J. Combinatorial Theory Ser. B 19 (1975), no. 2, 119–149. MR 432486, DOI 10.1016/0095-8956(75)90079-9
- Gerhard 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 228378, DOI 10.1073/pnas.60.2.438
Additional Information
- © Copyright 1977 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 226 (1977), 161-173
- MSC: Primary 05C10
- DOI: https://doi.org/10.1090/S0002-9947-1977-0437372-X
- MathSciNet review: 0437372