Premium
On the independence ratio of a graph
Author(s) -
Albertson Michael O.,
Hutchinson Joan P.
Publication year - 1978
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190020102
Subject(s) - mathematics , combinatorics , planar graph , contractible space , limiting , independence number , graph , discrete mathematics , independence (probability theory) , genus , triangulation , geometry , statistics , botany , mechanical engineering , engineering , biology
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.