Girth and Independence Ratio
Girth and Independence Ratio
Abstract Lower bounds are given for the independence ratio in graphs satisfying certain girth and maximum degree requirements. In particular, the independence ratio of a graph with maximum degree Δ and girth at least six is at least (2Δ − 1)/(Δ 2 + 2Δ − 1). Sharper bounds are given …