A note on the alternating number of independent sets in a graph

The independence polynomial of a graph G evaluated at −1, denoted here as I(G;−1), has arisen in a variety of different areas of mathematics and theoretical physics as an object of interest. Engström used discrete Morse theory to prove that |I(G;−1)|≤2^ϕ(G) where ϕ(G) is the decycling number of G , i.e., the minimum number of vertices needed to be deleted from G so that the remaining graph is acyclic. Here, we improve Engström's bound by showing |I(G;−1)|≤2^ϕ3(G) where ϕ₃(G) is the minimum number of vertices needed to be deleted from G so that the resulting graph contains no induced cycles whose length is divisible by 3. We also note that this bound is not just sharp but that every value in the range given by the bound is attainable by some connected graph.