Let $P$ be a fixed graph (hereafter called a ``pattern''), and let
$Subgraph(P)$ denote the problem of deciding whether a given graph $G$
contains a subgraph isomorphic to $P$. We are interested in
$AC^0$-complexity of this problem, determined by the smallest possible exponent
$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits of size
$n^{C(P)+o(1)}$. Motivated by the previous research in the area, we also
consider its ``colorful'' version $Subgraph_{col}(P)$ in which the target
graph $G$ is $V(P)$-colored, and the average-case version $Subgraph_{ave}(P)$
under the distribution $G(n,n^{-\theta(P)})$, where $\theta(P)$ is the
threshold exponent of $P$. Defining $C_{col}(P)$ and $C_{ave}(P)$ analogously
to $C(P)$, our main contributions can be summarized as follows.

1. $C_{col}(P)$ coincides with the tree-width of the pattern $P$ within a logarithmic factor.
This shows that the previously known upper bound by Alon, Yuster, Zwick is almost
tight.

2. We give a characterization of $C_{ave}(P)$ in purely combinatorial terms within a multiplicative factor of 2.
This shows that the lower bound technique of Rossman is essentially tight, for any
pattern $P$ whatsoever.

3. We prove that if $Q$ is a minor of $P$ then $Subgraph_{col}(Q)$ is
reducible to $Subgraph_{col}(P)$ via a linear-size monotone projection.
At the same time, we show that there is no monotone projection
whatsoever that reduces $Subgraph(M_3)$ to $Subgraph(P_3 +
M_2)$ ($P_3$ is a path on 3 vertices, $M_k$ is a matching with $k$
edges, and ``+'' stands for the disjoint union). This result strongly
suggests that the colorful version of the subgraph isomorphism problem is
much better structured and well-behaved than the standard (worst-case,
uncolored) one.