CS 571 Topics in Graph Theory & Algorithms Spring 2010
Instructor: Ugur Dogrusoz
Office, Hours: EA-528, Tue, Fri PM
Classroom, Hours: EA-502, Tue 15:40, Fri 13:40 & 14:40

  • HW 4 grades are now available. Averages for the homework assignments are 80, 71, 64, and 59 / 100, respectively.
  • Presentation guidelines is now available. Here is the LaTeX template to be used for the notes to be prepared.
    • [May 7] Section 1.9: Onur Sumer and Alper Karacelik
    • [May 7] Section 2.3: Muhsin Can Orhan and Seher Acer
    • [May 7] Section 2.4: Emre Varol and Cafer Yildirim
    • [May 14] Section 5.4: Emre Sermutlu and Yilmaz Degirmenci
    • [May 14] Section 5.5: Abdullah Atmaca and Mert Cetinkaya
    • [May 14] Section 6.1 and 6.2: Sefa Kilic
    • [May 14] Section 12.3: Enver Kayaaslan
  • Check here at least once a week!
Description This is normally a course on special topics in graph theory and algorithms, presenting a detailed study of certain research topics in these areas. This year fundamentals of graph theory will be covered along with certain graph theory applications as review topics if time permits.
Prerequisite Prior knowledge of fundamentals of computer science and graph theory required. Permission from the instructor required for undergraduates.
  • Become accomplished in formal / mathematical theorem proving using the fundamental techniques of construction, induction, and contradiction (as opposed to traditional/informal proof methods).
  • Learn the fundamentals of graph theory, which is an important mathematical tool in a wide variety of subjects from operational research and chemistry to genetics and linguistics, and from electrical engineering and geography to sociology, architecture, and computer science.
  • Become acquainted with the structure of graphs, and how to determine the relationship between graph invariants (such as order, size, or minimum degree) and a graph property (like being hamiltonian, containing a perfect matching).
  • Relate theory to practice through the study of certain graph theory applications.
Textbooks Required
  • Graph Theory by Reinhard Diestel, Springer, QA166.D51413 1997, ISBN 0-387-98211-6. electronic copy
  • Introduction to Graph Theory, 4th Edition by Robin J. Wilson, Logman Group Ltd., ISBN 0-582-24993-7.
  • Graph Theory by Ronald Gould, Benjamin-Cummings, QA166.G66 1988.
  • Graphs, Networks and Algorithms by Dieter Jungnickel, Springer, 1999, ISBN 3-540-63760-5.
  • Graph Theory Applications by L.R. Foulds, Springer-Verlag, 1991, ISBN 3-540-97599-3.
Outline &
Lecture Notes
Concepts Textbook
Foundations -
Basics Chapter 1
Matching Chapter 2
Connectivity Chapter 3
Planarity Chapter 4
Coloring Chapter 5
Hamilton Cycles Chapter 10
Grading Criteria:
Component Weight Date/Due
Homework 50 -
Final 30 in-class (EA 502, May 21, 13:30 - 16:30)
Presentation 20 (April 16, May 7 & 14)
Assignments & Exams
Homework Exams
HW 4 Solutions
HW 3 Solutions
HW 2 Solutions
HW 1 Solutions