COMP 560
Fall 200607

The text is Introduction to Graph Theory, by Douglas West. This is
available in the Book Store.
A reference is Graph Theory, by Reinhard Diestel. This is available
free from Diestel's website:
http://www.math.unihamburg.de/home/diestel/books/graph.theory/download.html
For background reading on graph algorithms, the textbook for COMP 360,
Cormen, Leiserson, Rivest, Stein, Introduction
to Algorithms, 2nd edition, is recommended. This book
is on reserve in the Schulich Library and is henceforth
referred to as CLRS.
Particular topics to review are:
 ch. 22.1 on representations of graphs: 527530;
 ch. 22.1 on Breadth First Search (BFS): pp. 531538;
 ch. 22.3 on Depth First Search (DFS): pp. 540547.
This material can also be found in the previous edition of the book, by Cormen, Leiserson, and Rivest (the ``white book''), but the chapter and page numbers are different.
Approximate Schedule (by lecture number)
1. Overview: mathematical beginnings, algorithmic beginnings, modern
developments, and modern applications. Getting started:
graph models, vertex degree
2. Paths and cycles: Hamilton cycles, Euler cycles, and some applications
34. Connectivity, applications of DFS
56. Trees, trees as models
78. Matchings and applications
supplemental reading: CLRS 26.12, pp. 644649
9. Problem session/review session
10. Midterm exam on Thursday, October 5 (possibly in the evening)
** No class on Tues. October 10 (follow a Monday schedule)
1112. Network Flows
1314. Planarity and Graph Layout
16. Colouring
17. Chordal Graphs
18. Path and Tree Decompositions
19. Fixed Parameter Tractable Algorithms for Colouring
2021. Special topics
2224. Student presentations
The midterm will be approximately Thurs. October 5,
possibly in the evening. The last class meets Tuesday, November 28.
Special topics (either for lecture or student presentations):
Introduction to perfect graphs and the perfect graph theorem
Spectral graph theory, eigenvalues and eigenvectors, the Laplacian, and
applications: spectral clustering methods
Application: Expanders in communication networks
Szemeredi's Regularity Lemma
Ramsey Theory
Random Graphs
World Wide Web graphs