Math 412
Introduction to Graph Theory
Sections X13 and X14
Instructor: Alexandr Kostochka
Office: 234 Illini Hall
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
E-mail:
kostochk@math.uiuc.edu
Time and place: 12pm-12:50pm MWF, Altgeld Hall
Final exam: 1:30-4:30 PM, Wednesday, December 17
Office hours: 3-4pm MWF (tentatively), and by
appointment
Class Announcements
NO CLASSES ON FRIDAYS NOVEMBER 14 AND NOVEMBER 21.
We have help sessions on Tuesdays from 5pm to 6:30pm
in Room 141 Altgeld Hall.
The tests will be on Thursdays,
November 13, and December 4. All tests will be
from 7pm to 8:30pm
in Room 143 Altgeld Hall.
Topics for Test 4 ( December 4) are:
1. Matchings in bipartite graphs. Hall's Theorem.
2. Matchings and covers. Konig-Egervary Theorem.
3. Matchings in general graphs. Tutte's 1-factor Theorem.
4. Berge-Tutte Formula and theorems of Petersen.
5. Connectivity and edge connectivity.
6. Menger's Theorems.
7. Flows in networks. Decomposition of every flow into flows along cycles and
s,t-paths.
8. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.
9. Colorings. Greedy algorithm for coloring.
10. Coloring of interval graphs.
11. Color-critical graphs and their properties ((k-1)-edge-connected etc.).
12. Brooks' Theorem.
13. Mycielski's Construction.
14. Turan's Theorem.
15. Planar and plane graphs. Dual graphs.
16. Bipartite plane graphs versus Eulerian dual graphs.
17. Maximal planar graphs and triangulations.
18. Outerplanar graphs.
19. Euler's Formula and its corollaries.
20. Kuratowski's Theorem.
To look at your grades, go to
``www.math.uiuc.edu'', then ``courses'', then ``scores reports''.
Last changed on November 17, 2008.