A graph
G is
well-covered if every maximal independent set has the same cardinality
q . Let
ik(G) denote the number of independent sets of cardinality
k in
G . Brown, Dilcher, and Nowakowski conjectured that the independence sequence
(i0(G),i1(G),…,iq(G)) was unimodal for any well-
covered graph
G with independence number
q. Michael and Traves disproved this conjecture. Instead they posited the so-called “Roller Coaster” Conjecture: that the terms
could be in any specified order for some well-
covered graph
G with independence number
q . Michael and Traves proved the conjecture for
q<8 and Matchett extended this to
q<12.
In this paper, we prove the Roller Coaster Conjecture using a construction of graphs with a property related to that of having a maximal-clique partition. In particular, we show, for all pairs of integers 0≤k<q and positive integers m, that there is a well-covered graph G with independence number q for which every independent set of size k+1 is contained in a unique maximal independent set, but each independent set of size k is contained in at least m distinct maximal independent sets.