On the independence ratio of a graph
- 1 March 1978
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 2 (1) , 1-8
- https://doi.org/10.1002/jgt.3190020102
Abstract
This paper presents some recent results on lower bounds for independence ratios of graphs of positive genus and shows that in a limiting sense these graphs have the same independence ratios as do planar graphs. This last result is obtained by an application of Menger's Theorem to show that every triangulation of a surface of positive genus has a short cycle which does not separate the graph and is non‐contractible on that surface.Keywords
This publication has 9 references indexed in Scilit:
- The Independence Ratio and Genus of a GraphTransactions of the American Mathematical Society, 1977
- The independence ratio and genus of a graphTransactions of the American Mathematical Society, 1977
- A lower bound for the independence number of a planar graphJournal of Combinatorial Theory, Series B, 1976
- Every planar map is four colorableBulletin of the American Mathematical Society, 1976
- The maximum size of an independent set in a nonplanar graphBulletin of the American Mathematical Society, 1975
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEMProceedings of the National Academy of Sciences, 1968
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941
- Zur allgemeinen KurventheorieFundamenta Mathematicae, 1927