  Sparse-dense partitions was introduced by Feder, Hell, Klein, and Motwani
[STOC 1999, SIDMA 2003] as a tool to solve partitioning problems. In this
paper, the following result concerning independent sets in graphs having
sparse-dense partitions is presented: if a $n$-vertex graph $G$ admits a
sparse-dense partition concerning classes $\mathcal S$ and $\mathcal D$, where
$\mathcal D$ is a subclass of the complement of $K_t$-free graphs (for some
~$t$), and graphs in $\mathcal S$ can be recognized in polynomial time, then:
  enumerate all maximal independent sets of $G$ (or find its maximum) can be
performed in $n^{O(1)}$ time whenever it can be done in polynomial time for
graphs in the class $\mathcal S$.
  This result has the following interesting implications:
  A P versus NP-hard dichotomy for Max. Independent Set on graphs whose vertex
set can be partitioned into $k$ independent sets and $\ell$ cliques, so-called
$(k, \ell)$-graphs. concerning the values of $k$ and $\ell$ of $(k,
\ell)$-graphs.
  A P-time algorithm that does not require $(1,\ell)$-partitions for
determining whether a $(1,\ell)$-graph $G$ is well-covered. Well-covered graphs
are graphs in which every maximal independent set has the same cardinality.
  The characterization of conflict graph classes for which the conflict version
of a P-time graph problem is still in P assuming such classes. Conflict
versions of graph problems ask for solutions avoiding pairs of conflicting
elements (vertices or edges) described in conflict graphs.
