Livros de teoria dos grafos

John Adrian Bondy, U.S. Rama Murty, Graph Theory, Springer, 2007.
Béla Bollobás, Graph Theory: an Introductory Course, Springer-Verlag, 1979.
Béla Bollobás, Modern Graph Theory, Springer-Verlag, 1998.
Edição ampliada do Graph Theory: an Introductory Course do mesmo autor.
Reinhard Diestel, Graph Theory, 3rd. ed., Springer, 2000.
László Lovász, Michael D. Plummer, Matching Theory, North-Holland, 1986.
Tudo sobre emparelhamentos e muito mais. Excelente! (Mas o índice remissivo poderia ser melhor...)
László Lovász, Combinatorial Problems and Exercises, 2nd. ed., North-Holland, 1993.
Aprenda teoria dos grafos fazendo exercícios. Alguns dos exercícios estão resolvidos; muitos são acompanhados de sugestões e dicas.
Norman Biggs, Algebraic Graph Theory, Cambridge University Press, 1974.
Chris Godsil, Gordon Royle, Algebraic Graph Theory, Springer, 2001.
Robin J. Wilson, Introduction to Graph Theory, 4th.ed., Prentice Hall, 1996.
Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson, Graph Theory 1736–1936, Claredon Press, 1976.
História da teoria dos grafos, com reprodução de alguns artigos seminais clássicos.
Martin Aigner, Günter M. Ziegler, Proofs from the book, Springer, 1998.

Antigos clássicos

John Adrian Bondy, U.S. Rama Murty, Graph Theory with Applications, Macmillan/Elsevier, 1976.
Antigo, mas continua muito bom.
Claude Berge, The Theory of Graphs and Its Applications, Mathuen & John Wiley, 1962.
Frank Harary, Graph Theory, Addison-Wesley, 1972.
F.S. Roberts, Discrete Mathematical Models with Applications to Social, Biological and Environmental Problems, Prentice-Hall, 1976.
F.S. Roberts, Graph Theory and its Application to Problems of Society, NFS-CBMS monograph 29, SIAM, 1978.

Paulo Feofiloff, Exercícios de Teoria dos Grafos, 2005.
Cláudio L. Lucchesi, Introdução à Teoria dos Grafos, 12º Colóquio Brasileiro de Matemática, IMPA, 1979.
Douglas B. West, Introduction to Graph Theory, 2nd. ed., Prentice Hall, 2001.
Gary Chartrand, Linda Lesniak, Graphs and Digraphs, 4th. ed., Chapman&Hall/CRC, 2005.
Martin Aigner, Günter M. Ziegler, Proofs from the book, Springer, 1998.
Tommy R. Jensen e Bjarne Toft, Graph Coloring Problems, John Wiley, 1995.

David Harel, Algorithmics: The Spirit of Computing, 2nd. ed., Addison-Wesley, 1992.
Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
Michael R. Garey, David S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.