22C:137, 22M:152 Theory of Graphs
10:5512:10 TTh Room 114 MLH
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 3193532956
Office Hours: 23 MWF
Teaching Assistant:
Rajiv Raman
101L MLH, rraman@cs.uiowa.edu, 3193532353
Office Hours: 34 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.
Sources:
 Text book: Reinhard Diestel, Graph Theory, Second Edition,
SpringerVerlag, New York, Graduate Texts in Mathematics, Volume 173.
There is a free searchable and hyperlinked electronic edition of the book
here,
which may be viewed online or downloaded for offline use.

Supplementary reading:
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
here.
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 (cremer@cs.uiowa.edu, 3193351713, 14D McLean Hall).
Consult the college policy on Student Complaints
Concerning Faculty Actions (online version)
for more information.
Grading Policy,
Announcements,
Homeworks and Exams,
Topics,
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.
 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.
This is a tentative list of topics we will study in the course.

Flows, Connectivity, Matching.
 Maxflow mincut theorem
 Hall's theorem for bipartite matching and Tutte's 1factor theorem
 Menger's theorem and Mader's theorem on graph connectivity
 NashWilliam's theorem on edgedisjoint spanning trees
 Matroid theory and approximation algorithms for connectivity problems

Graph Coloring
 Brook's theorem for vertex coloring
 Vizing's theorem for edge coloring
 5colorability of planar graphs
 List coloring: 5choosability of planar graphs
 Perfect graphs and characterizations
 The ellipsoid algorithm for coloring perfect graphs

Random 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: ErdosStone Theorem
 Topological minors: the result of BollobasThomason and KomlosSzemeredi
 Hadwiger's conjecture