The primary focus of this dissertation is to establish the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. Motivated by Ehrenfeucht-Fraïssé games for monadic second-order logic, we study the complexity of problems of the following sort: When is there a vertex-colored graph with a given set of neighborhoods?

More precisely, fix a radius ρ and let N( G) be the set of isomorphism classes of ρ-neighborhoods of vertices of G, where G is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. Given a set S of pointed, colored graphs, when is there a graph G with N(G) = S? Or N(G) ⊂ S? What if G is forced to be finite, or connected, or both?

If the neighborhoods are unrestricted, all these problems are recursively unsolvable; this follows from the work of Bulitko but we give a simpler, independent proof in the colored case. In contrast, when the neighborhoods are cycle free, we show that all the problems are in the class P. Surprisingly, if G is required to be a regular (and thus infinite) tree, the realization problem is NP-complete (for degree 3 or higher). Finally, we extend the former results to a slightly more general class of neighborhoods called bouquet neighborhoods.