Independent Sets in n-Vertex k-Chromatic l-Connected Graphs

Authors

John Engbers, Marquette UniversityFollow
Lauren Keough, Grand Valley State University
Taylor Short, Grand Valley State University

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.

Comments

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

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