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