Background:

In the last twenty years several applications of Logic, in particular Model theory, to problems in Combinatorics emerged. Among them we have

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