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.