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 A C 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 Subgrap h co l ( P ) in which the target graph G is V ( P ) -colored, and the average-case version Subgrap h ave ( P ) under the distribution G ( n n − ( P ) ) , where ( P ) is the threshold exponent of P . Defining C co l ( P ) and C ave ( P ) analogously to C ( P ) , our main contributions can be summarized as follows.

1. C co l ( 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 Subgrap h co l ( Q ) is reducible to Subgrap h co l ( 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.