#### Document Type

Article

#### Publication Date

7-2021

#### Publisher

Elsevier

#### Source Publication

Discrete Mathematics

#### Source ISSN

0012-365x

#### Abstract

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.

#### Recommended Citation

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.

https://epublications.marquette.edu/math_fac/72

## Comments

Accepted version.

Discrete Mathematics, Vol. 344, No. 7 (July 2021): 112376. DOI. © 2021 Elsevier. Used with permission.