We study the problem of maximizing the number of independent sets in n-vertex k-chromatic ℓ-connected graphs. First we consider maximizing the total number of independent sets in such graphs with n sufficiently large, and for this problem we use a stability argument to find the unique extremal graph. We show that our result holds within the larger family of n-vertex k-chromatic graphs with minimum degree at least ℓ, again for n sufficiently large. We also maximize the number of independent sets of each fixed size in n-vertex 3-chromatic 2-connected graphs. We finally address maximizing the number of independent sets of size 2 (equivalently, minimizing the number of edges) over all n-vertex k-chromatic ℓ-connected graphs.
Engbers, John; Keough, Lauren; and Short, Taylor, "Independent Sets in n-Vertex k-Chromatic l-Connected Graphs" (2021). Mathematical and Statistical Science Faculty Research and Publications. 72.