Edge density and independence ratio in triangle-free graphs with maximum degree three (Q1917491)

Let \(G = (V,E)\) be a graph, and let \(n = |V(G) |\) and \(m = |E(G) |\) be the number of vertices and number of edges in \(G\), respectively. The edge density of \(G\) is defined by \(c = m/n\). An independent set of a graph \(G\) is a set \(S\) of vertices such that no two vertices of \(S\) are adjacent in \(G\). The independence number of a graph \(G\) is the largest number of pairwise nonadjacent vertices in \(G\). The authors present a simple polynomial-time algorithm to compute independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. The size of the independent set computed by the algorithm increases as the edge density decreases from 3/2 to 1, thereby establishing new lower bounds of the independence number of these graphs.