Counting Independent Sets and Generalized Colorings in Graphs with Various Restrictions

<p>An n-vertex, d-regular graph can have at most 2^(n/2+o(n)) independent sets. We address this upper bound when we impose the additional condition that the graph has independence number at most ?. In particular, we show that for a sequence of d_n-regular n-vertex graphs G_n with independence number at most ?_n, if d_n ? 8 and (?_n)/n ? c_? where 0 < c_? = 1/2, then G_n has at most k(c_?)^(n+o(n)) independent sets, where k(c_?) is an explicit constant which we show is as small as possible. We also prove an analogous result when 1/2 < c_? < 1, subject to the additional condition that (d_n)/n ? c_d, where 0 < c_d = 1 - c_?. Our proofs use both graph container arguments and constructive techniques. We further refine our results by giving the asymptotic behavior of the maximum number of independent sets of a fixed size scaling with n of an n-vertex d-regular graph with independence number at most ?. Finally, we consider some exact results on maximizing the number of graph homomorphisms from an n-vertex graph G with independence number ? to certain target graphs. We conclude by considering some open questions about proper q-colorings.</p>