Graph Theory - 0366.3267
Procedural Matters:
Prerequisite Courses:
Discrete Mathematics or Introduction to Combinatorics and Graph
Theory, Linear Algebra, Introduction to Probability.
Exercises will be given during the course and will account for 10% of the
final grade.
There will also be a final exam.
Text books:
Most of the topics covered in the course appear in the
books listed below (especially the first three).
Graph Theory,
by J. A. Bondy and U. S. R. Murty,
Springer, 2008.
Introduction to Graph Theory,
by D. B. West,
Prentice Hall, 1996.
Graph Theory,
by R. Diestel,
Springer, 1997.
The Probabilistic Method, third edition,
by N. Alon and J. H. Spencer, Wiley, 2008.
Brief syllabus:
Graphs and subgraphs, trees, connectivity, Euler tours,
Hamilton cycles, matchings, Hall's Theorem and Tutte's Theorem,
edge coloring and Vizing's Theorem,
independent sets, Turan's Theorem and Ramsey's Theorem,
vertex coloring, planar graphs, directed graphs,
probabilistic methods and linear algebra tools in Graph Theory.