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

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.

Sources:

• 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 here, which may be viewed on-line 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, 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

Announcements

Homeworks and Exams

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

List of Topics