G. Gottlob, P. Kolaitis, T. Schwentick: "Existential second-order logic over graphs: Charting the tractability frontier"; Journal of the ACM, 51 (2004), 2; 312 - 362.
http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04968639