Graph Theory & Applications
Ioan Tomescu

1) Basic definitions. Trees. Cyclomatic and cocyclomatic numbers of a graph. Kruskal's algorithm for minimum spanning tree.
2) Eulerian and bipartite graphs. Characterization theorems.
3) Planar graphs and convex polyhedra. Euler's formula and the five colour theorem.
4) Flows in networks. Ford-Fulkerson's theorem and algorithm for integer capacities. Applications to bipartite graphs.
5) Flows of minimum cost in networks.
6) h-Connected graphs and Menger's theorems.
7) Colouring problems: greedy algorithm, Brook's theorem, chromatic index of a bipartite graph and applications to Clos networks. Chromatic polynomials.
8) The spectrum of a graph and the adjacency algebra; Hoffman's theorem and spectra of regular graphs.Harary's theorem.

References
1) B.Bollobas, Modern graph theory, Springer-Verlag, New York,1998.
2) M.Behzad, G.Chartrand, L.Lesniak-Foster, Graphs & digraphs, Wadsworth,1979.
3) N.Biggs, Algebraic graph theory, Cambridge University Press,1974.
4) R.E.Tarjan, Data structures and network algorithms, SIAM, Philadelphia,1989.
5) I.Tomescu, Problems in combinatorics and graph theory, J.Wiley,New York,1985.