CSC 2410, Introduction to Graph Theory, Fall 2017

Final Exam:   Tuesday Dec 12, 1-4, Bahen 2145.  This is an open book exam.  You can bring a copy of the text, but you cannot bring any written notes.   There should not be any written notes inside the text - if you already have writing in the text, show it to me before the exam.


The text is "Introduction to Graph Theory" by Doug West (Second edition).

Syllabus



Assignments:
 

Assignment 1 is due on Tuesday Oct 10 before 11:00 AM.  Solutions will be discussed later that day in the lecture.

Assignment 2 is due on Tuesday Nov 7 before 10:00 AM.  Solutions will be discussed later that day in the lecture.

Assignment 3 is due on Tuesday Dec 5 before 10:00 AM.  Solutions will be discussed later that day in the lecture.

Lectures:

Sept 12: Chapter 1.   Read Chapter 2.

Sept 19: We start matchings.  Chapter 3.

Sept 26: More matchings. Chapter 3

Oct 3: Edmonds matching algorithm, f-factors. Chapter 3.  Then we begin  connectivity and network flows. Chapter 4

Oct 10:  More connectivity and network flows.  Chap 4. 

Oct 17: Colourings.  Chap 5

Oct 24:  More colourings:  Brooks Theorem, critical graphs. (sections 5.1, 5.2) perhaps edge colouring (section 7.1)

Oct 31:  List colouring(pages 408-412).  Planar graphs. Chapter 6

Nov 7: More planar graphs. Chap 6

Nov 14: The four colour theorem.  Chap 6

Nov 21: Hamiltonicity

Nov 28: The probabilistic method

 OFFICE HOURS: by appointment.  Send me email, and we can usually set up a time, often on short notice. If many of you request that I set up regular office hours, I will do so.

Old Final Exams:  2014, 2015