Schedule

This schedule is tentative and will likely change as the semester progresses. All sections are from the text by West, 2nd edition. 24 sections potentially. So with about 15 weeks, we have to average about 1.5 sections per week.

Date	Week	Due	Section
Jan 17	Week 1		Appendix A (read/skim).
Jan 22-26	Week 2	HW1	Section 1.1: Graph isomorphisms, special families of graphs.
Jan 29-Feb 1	Week 3	HW2	Section 1.2: Walks, trails, paths and cycles. Connectedness, Bipartite graphs.
Feb 5-Feb 9	Week 4		Section 1.3: Eulerian Circuits, Counting arguments and extremal problems. Graphic sequences, Havel-Hakimi theorem.
Feb 12-Feb 16	Week 5	HW3	Finish Section 1.3 and Start Section 1.4: Digraphs, winning strategies in Nim, Kings in Round-Robin tournaments.
Feb 19-Feb 23	Week 6		Finish Section 1.4 and Start Section 2.1: Trees! Spanning Trees. Trees and Distance.
Feb 26-Mar 1	Week 7	HW4	Finish Section 2.1 and Start Section 2.2: Spanning Trees. Trees and Distance.
Mar 4-Mar 8	Week 8	HW5	Section 2.2: Graceful labelings and Eulerian Digraphs
Mar 11-Mar 15	Week 8	HW5	Spring break
Mar 18-Mar 22	Week 8	HW5	Finish 2.2. Start Section 2.3: Kruskal and Dijkstra
Mar 25-Mar 29	Week 8	HW5	Finish 2.3: Start 3.1: Matchings and Covers. MIDTERM
Apr 01-Apr 05	Week 8	HW5	3.2: Hungarian algorithm, Start 4.1: Cuts and Connectivity
Apr 08-Apr 12	Week 8	HW5	Finish 4.1, 4.2: Menger’s Theorem.
Apr 15-Apr 19	Week 8	HW5	4.3: Flow problems. Ford-Fulkerson. 5.1: Graph colorings.
Apr 22-Apr 26	Week 8	HW5	5.1 and 5.2: Mycielski’s construction of graphs with large chromatic number.

If we do things properly, we cannot see Kuratowski’s theorem. But maybe we can see this in a project.

Old Schedule

Week of Jan 9

Thursday, Jan 13 first day of class

Section 1.1 + Appendix A (read/skim).: Topics from Appendix A to be reviewed as necessary.

Basic definitions and remarks about applications.

Week of Jan 16

Section 1.1: Graph isomorphisms, special families of graphs.

Week of Jan 23

Section 1.2: Walks, trails, paths and cycles. Connectedness, Bipartite graphs.

Week of Jan 30

Section 1.3: Eulerian Circuits, Counting arguments and extremal problems.; Graphic sequences, Havel-Hakimi theorem.

Week of Feb 6

Section 1.4: Digraphs, tournaments.

Week of Feb 13

Section 2.1: Spanning trees.; Trees and distance.

Week of Feb 20

Section 2.2, 2.3: Cayley’s Theorem and the Matrix Tree Theorem.; Optimization and trees, Kruskal’s algorithm.

Week of Feb 27

Section 2.3, 3.1: Dijkstra’s algorithm.; Matchings and Covers.

Midterm: Thursday, Mar 2 in class

Week of Mar 6

Spring break no classes

Week of Mar 13

Section 3.1, 3.2: Matchings and Covers.; Maximum and weighted bipartite matchings.

Week of Mar 20

Section 3.2, 4.1: Hungarian algorithm.; Cuts and connectivity.

Week of Mar 27

Section 4.1, 4.2: Cuts and Connectivity.; 2-connectivity, Menger’s Theorem.

Week of Apr 3

Section 4.2, 4.3: Menger’s Theorem.; Network Flow Problems.

Week of Apr 10

Section 4.3, 5.1: Max flow/min cut theorem, Ford-Fulkerson algorithm.; Graph colorings, Brook’s Theorem.

Week of Apr 17

Section 5.2, 5.3: Mycielski’s construction of graphs with large chromatic number.; Turan’s Theorem.; Chromatic Polynomial.

Week of Apr 24

Section 6.1, 6.2, 6.3: Planar graphs.; Characterization of planarity: Kuratowski’s Theorem.; Five and Four Color Theorems.

April 25 last day of class

Final Exam: TBD