22C:137, 22M:152 Theory of Graphs

10:55-12:10 TTh Room 114 MLH

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 2-3 MWF

Teaching Assistant: Rajiv Raman
101L MLH, rraman@cs.uiowa.edu, 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.


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, 319-335-1713, 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

Grading Policy

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%.


Homeworks and Exams

List of Topics

This is a tentative list of topics we will study in the course.
  1. 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

  2. Graph Coloring
    • 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

  3. 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

  4. 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