22C:137, 22M:152 Theory of Graphs
10:55-12:10 TTh Room 114 MLH
Sriram V. Pemmaraju
101G MLH, email@example.com, 319-353-2956
Office Hours: 2-3 MWF
101L MLH, firstname.lastname@example.org, 319-353-2353
Office Hours: 3-4 TTh
This course is aimed at graduate
students in computer science and mathematics and at advanced undergraduates
who have 22C:31 (or equivalent) or 22M:50 (or equivalent).
It will cover a mixture of classical material in graph theory
and some recent results (for example, on power law graphs). A tentative
list of topics is given below. For each main topic, I will attempt to present
at least one significant algorithmic result.
- Text book: Reinhard Diestel, Graph Theory, Second Edition,
Springer-Verlag, New York, Graduate Texts in Mathematics, Volume 173.
There is a free searchable and hyperlinked electronic edition of the book
which may be viewed on-line or downloaded for offline use.
Doug West, Introduction to Graph Theory, Second Edition,
Prentice Hall 2001.
- Additional journal papers. I will post details as the semester progresses.
I am using Schrijver's notes for matroid theory.
You can find these and other interesting stuff at his homepage.
Here is a local copy of these notes.
I need to hear from anyone who has a disability, which may require some
modification of seating, testing or other class requirements so that
appropriate arrangements may be made. Please see me after class or during
my office hours.
This course is run by the College of Liberal Arts and Sciences.
This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by
the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive
the approval of the Dean of the College of Liberal Arts and Sciences.
Details of the University policy of cross enrollments may be found online
If you have any complaints or concerns about how the course is being conducted,
please feel free to talk to me.
You are also welcome to get in touch the the Computer Science department chair,
Prof. Jim Cremer (email@example.com, 319-335-1713, 14D McLean Hall).
Consult the college policy on Student Complaints
Concerning Faculty Actions (online version)
for more information.
Homeworks and Exams,
Schedule and Plans
Plus/Minus grading will be used for the course.
There will be 4 homeworks, a midterm, and a final exam.
Each homework will be wortht 15% of your grade and each exam
will be worth 20%.
- The midterm exam will be handed out in class on Tuesday, 3/22
and will be due back on Thursday, 3/24.
- Redo problem 4 on the midterm exam and turn it in on 4/26, along with
Homework 2. Also, turn in your graded midterm so that we can update your scores.
This is a tentative list of topics we will study in the course.
- Homework 1, due: 3/1.
- Homework 1 Solution.
Problems 3, 4, 5, 6, and 8 were graded.
- Homework 2, due: 4/26.
- Midterm Solution, Problems 1, 2, and 3.
- Final Exam, due 5/12.
- Homework 2 Solution .
Problems 3, 4, 5, 6, and 7 were graded.
Flows, Connectivity, Matching.
- Max-flow min-cut theorem
- Hall's theorem for bipartite matching and Tutte's 1-factor theorem
- Menger's theorem and Mader's theorem on graph connectivity
- Nash-William's theorem on edge-disjoint spanning trees
- Matroid theory and approximation algorithms for connectivity problems
- Brook's theorem for vertex coloring
- Vizing's theorem for edge coloring
- 5-colorability of planar graphs
- List coloring: 5-choosability of planar graphs
- Perfect graphs and characterizations
- The ellipsoid algorithm for coloring perfect graphs
- The probabilistic method: existence of high girth, high chromatic number graphs
- Simple properties of almost all graphs
- Threshold functions and second moments
- The Phase transition
- Power law graphs, small world networks, and their properties
Extremal Graph Theory
- Turan's theorem on the existence of large cliques
- Szemeredi's Regularity Lemma
- Applying the Regularity Lemma: Erdos-Stone Theorem
- Topological minors: the result of Bollobas-Thomason and Komlos-Szemeredi
- Hadwiger's conjecture