Background:

• 0-1 laws and their variations
  This is well summarized in the book by J. Spencer [Spen].
• Modular linear recurrence relations for combinatorial counting functions (The Specker-Blatter Theorem)
  This theorem has remained widely unnoticed, and deserves wider attention and further study [Spec,Fisc,FM].
• Recent progress in undertanding the ultimate periodicity of finite spectra by Y. Gurevich and S. Shelah, and E. Fischer and J.A. Makowsky [FMa].
• Applications of meta-theorems which apply to whole families of combinatorial problems, instead of just specific problems.
  This was pioneered by B. Courcelle and S. Arnborg, J. Lagergren and D.Seese, in applications of definability in Monadic Second Order Logic to graph algorithms, and summarized in J.A. Makowsky [Mak] and M. Grohe [Groh].
• The use of definability criteria in the study of graph polynomials (Tutte polynomial and its relatives, matching polynomials, generalized chromatic polynomials) introduced by J.A. Makowsky [Maka], and further developed together with B. Zilber [MZ]. See also [Makb,FMb].
• The use of model theoretic methods in designing algorithms for the computation of forbidden minors, [AGK].
• The realization that virtually all graph polynomials of the literature can be viewed as combinatorial counting functions which occur inside models of omega-stable omega-categorical theories, J. Makowsky and B. Zilber [MZ].
• The use of model theory to unify results in extremal combinatorics, as in A. Razborov [Raz].
• Recent work on the classification and characterization of partition functions by L. Lovasz and B. Szegedy and their collaborators [FLS,Sz], and their complexity, cf. [BuGr].
• The use of ultraproducts in the proof of the Regularity Lemma by B. Szegedy and G. Elek [ES].

References:

[ADK] I. Adler, M. Grohe and S. Kreutzer, Computing Excluded Minors, 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2008, 641-650.

[BuGr] A. Bulatov and M. Grohe, The complexity of partition functions, Theoretical Computer Science, 348 (2005), pp. 148-186.

[ES] G. Elek and B. Szegedy, Limits of Hypergraphs, Removal and Regularity Lemmas. A Non-standard Approach, arXiv:0705.2179.

[Fisc] E. Fischer, The Specker-Blatter theorem does not hold for quaternary relations, Journal of Combinatorial Theory Series A 103 (2003), 121-136.

[FM] E. Fischer and J. A. Makowsky, The Specker-Blatter Theorem revisited, Proceedings of the 9th COCOON (2003), 90-101.

[FMa] E. Fischer and J. A. Makowsky, On spectra of sentences of monadic second order logic with counting, Journal of Symbolic Logic 69 (2004), 617-640.

[FMb] E. Fischer and J.A. Makowsky, Linear Recurrence Relations for Graph Polynomials, in: Special volume of LLNCS in honour of Boris (Boaz) A. Trakhtenbrot on the occasion of his 85th birthday. LNCS 4800 (2008) pp. 266-279

[FLS] M. Freedman, L. Lovasz and A. Schrijver: Reflection positivity, rank connectivity, and homomorphism of graphs, J. AMS 20 (2007)

[Groh] M.Grohe, Logic, Graphs, and Algorithms, Preprint 2007 http://www2.informatik.hu-berlin.de/~grohe/pub/meta-survey.pdf

[Mak] J.A. Makowsky, Algorithmic aspects of the Feferman-Vaught Theorem, Annals of Pure and Applied Logic, 126 (1-3) April 2004, pp. 159-213.

[Maka] J.A. Makowsky, Coloured Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width, Discrete Applied Mathematics 145 (2005) pp. 276-290

[Makb] J.A. Makowsky, From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials, Theory of Computing Systems, 2008 online available at: http://www.springerlink.com/content/p651v22676071442/?p=c6b8fee80c03417ea13428404b6086c1&pi=64

[MZ] J.A. Makowsky and B. Zilber, Polynomial invariants of graphs and totally categorical theories, Preprint 2006, MODNET, http://www.logique.jussieu.fr/modnet/Publications/Preprint%20server/papers/21/index.php

[Raz] A. Razborov, Flag Algebras, Journal of Symbolic Logic, 72.4 (2007, pp. 1239-1282.

[Spen] J. Spencer, The Strange Logic of Random Graphs, Springer 2001

[Spec] E. Specker, Application of Logic and Combinatorics to Enumeration Problems, in: Trends in Theoretical Computer Science, E. B{\"o}rger ed., Computer Science Press, 1988, 141-169, Reprinted in: Ernst Specker, Selecta, Birkh\"auser 1990, pp. 324-350

[Sz] B. Szegedy, Edge coloring models and reflection positivity. math.CO/0505035