CS 570 Graph Theory Spring 2012 Instructor: Ugur Dogrusoz Office, Hours: EA-429, Wed, Thu PM Classroom, Hours: EB-204, Wed 13:40 & 14:40, Fri 15:40

Announcements	HW 5 solutions are now available Final solutions are now available Unless otherwise stated, we do not hold the following lecture hour: Fri 16:40-17:30 Check here at least once a week!
Description	Fundamentals of graph theory will be covered along with certain graph theory applications as review topics if time permits. Topics include paths and searching, trees, networks, cycles, planarity, matching, and independence.
Prerequisite	Prior knowledge of fundamentals of computer science or graph theory required. Permission from the instructor required for undergraduates.
Objectives	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, ISBN-13: 978-3642142789. electronic copy Recommended 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. Supplementary 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 Flows Chapter 6 Hamilton Cycles Chapter 10
Grading	Grading Criteria: Component Weight Date/Due Attendance 05 - Homework 60 - Midterm 15 in-class (Apr 4, 2012, 13:00-15:30) Final 20 in-class (May 2, 2012, 13:00-15:30)
Assignments & Exams	Homework Exams HW 5 Solutions HW 4 Solutions HW 3 Solutions HW 2 Solutions Final Solutions HW 1 Solutions Midterm Solutions