  A fundamental graph problem is to recognize whether the vertex set of a graph
$G$ can be bipartitioned into sets $A$ and $B$ such that $G[A]$ and $G[B]$
satisfy properties $\Pi_A$ and $\Pi_B$, respectively. This so-called
$(\Pi_A,\Pi_B)$-Recognition problem generalizes amongst others the recognition
of $3$-colorable, bipartite, split, and monopolar graphs. In this paper, we
study whether certain fixed-parameter tractable $(\Pi_A,\Pi_B)$-Recognition
problems admit polynomial kernels. In our study, we focus on the first level
above triviality, where $\Pi_A$ is the set of $P_3$-free graphs (disjoint
unions of cliques, or cluster graphs), the parameter is the number of clusters
in the cluster graph $G[A]$, and $\Pi_B$ is characterized by a set
$\mathcal{H}$ of connected forbidden induced subgraphs. We prove that, under
the assumption that NP is not a subset of coNP/poly,
\textsc{$(\Pi_A,\Pi_B)$-Recognition} admits a polynomial kernel if and only if
$\mathcal{H}$ contains a graph with at most $2$ vertices. In both the
kernelization and the lower bound results, we exploit the properties of a
pushing process, which is an algorithmic technique used recently by Heggerness
et al. and by Kanj et al. to obtain fixed-parameter algorithms for many cases
of $(\Pi_A,\Pi_B)$-Recognition, as well as several other problems.
