  A tessellation of a graph is a partition of its vertices into vertex disjoint
cliques. A tessellation cover of a graph is a set of tessellations that covers
all of its edges, and the tessellation cover number, denoted by $T(G)$, is the
size of a smallest tessellation cover. The \textsc{$t$-tessellability} problem
aims to decide whether a graph $G$ has $T(G)\leq t$ and is
$\mathcal{NP}$-complete for $t\geq 3$. Since the number of edges of a maximum
induced star of $G$, denoted by $is(G)$, is a lower bound on $T(G)$, we define
good tessellable graphs as the graphs~$G$ such that $T(G)=is(G)$. The
\textsc{good tessellable recognition (gtr)} problem aims to decide whether $G$
is a good tessellable graph. We show that \textsc{gtr} is
$\mathcal{NP}$-complete not only if $T(G)$ is known or $is(G)$ is fixed, but
also when the gap between $T(G)$ and $is(G)$ is large. As a byproduct, we
obtain graph classes that obey the corresponding computational complexity
behaviors.
