CS150-GT
Graph Theory
Spring 2023
The Petersen graph labeled as a Kneser graph
CS150-GT
|
The Petersen graph labeled as a Kneser graph |
STCs: JCC 270, 6:00-7:15pm
Instructor: Michael Jahn (Michael.Jahn@tufts.edu)
CA: Adam Xu (Adam.Xu@tufts.edu)
Office Hours:
| Michael Jahn: | 1:00-3:00pm Fri in JCC 320
also Tues after 12:00 is ok, but email me beforehand. I don't have a room booked, but we can probably go to the HRI Lab (conference room?) |
| Adam Xu: | 4:30-6:30pm Note: Adam's Tues office hours are cancelled, but you can still make an appointment with Michael Jahn if you need office hours on Tuesdays. |
Text: Introduction to Graph Theory, 2e, by Douglas West
Other texts you might look at:
Grading:
HW, Handouts, etc.: will be posted at https://www.cs.tufts.edu/comp/150GT/documents/
Homework: PDF submission to Gradescope. LaTeX preferred. Please no scans of handwritten solutions.
Project: There is no required programming in this course. But your project may be an implementation, or it may be a theoretical project.
Guidelines for write-ups: On any HW or Project (even on an Exam, as much as possible) you should present your solution with your fellow students in mind as the audience, not me. Level-of-detail is determined by what your classmates need to see, in order to understand your solution without having to solve the problems for themselves.
| Week 1 | ||
| L1 Wed, 18 Jan 2023 |
§1.1 | intro/def of graphs
hw1-including-pics.zip hw1.pdf hw1.tex |
| Week 2 | ||
| L2 Mon, 23 Jan 2023 |
§1.1 | isomorphism
walks, trails, paths |
| L3 Wed, 25 Jan 2023 |
§1.2 | connected, cut-edge, closed odd walk contains odd cycle
indep set, bipartite graph, G bipartite iff no odd cycle hw2.pdf hw2.tex |
| Week 3 | ||
| L4 Mon, 30 Jan 2023 |
§1.2 §1.3 |
QUIZ 1
Eulerian circuits Handshaking lemma |
| L5 Wed, 1 Feb 2023 |
§1.3 | Counting cycles,
vertex deletions, graphic sequences hw3.pdf hw3.tex |
| Week 4 | ||
| L6 Mon, 6 Feb 2023 |
§1.3, §2.1 |
extremal problems,
trees and distance |
| L7 Wed, 8 Feb 2023 |
§2.2, p.81 |
QUIZ 2
Prufer sequences (for counting labeled trees) hw4.pdf hw4.tex |
| Week 5 | ||
| L8 Mon, 6 Feb 2023 |
§2.3, p.101
§2.2, p.87 |
Huffman codes
Graceful labeling See also graceful-labeling-algorithms-and-complexity.pdf, and the standard reference on labeling, Gallian's ongoing survey (currently in its 25th edition). There's a link to the pdf on that page. |
| L9 Wed, 15 Feb 2023 |
§2.1 |
QUIZ 3
distance, diameter, eccentricity, radius, center, Weiner index hw5.pdf hw5.tex |
| Week 6 | ||
| Mon, 20 Feb 2023 | HOLIDAY (Presidents' Day) | |
| L10 Wed, 22 Feb 2023 |
§5.1 | vertex colorings, χ(G), k-critical, α(G), ω(G), join, cartesian product |
| L11 THU, 23 Feb 2023 |
§5.1
§5.2 |
Brooks' Theorem
The paper Brooks' Theorem and Beyond.pdf gives a proof of Brooks using Kempe-chains, along with several other proofs using different approaches. |
| Week 7 | ||
| Mon, 27 Feb 2023 | EXAM 1 (on material up through Feb 15 in class, Chapters 1, 2) | |
| L 12 Wed, 1 Mar 2023 |
§5.2
§5.3 |
Mycielski's construction
χG(k) = chromatic polynomial (of a graph G) hw6.pdf hw6.tex |
| Week 8 | ||
| L 13 Mon, 6 Mar 2023 |
§6.1 | Planar embeddings |
| L 14 Wed, 8 Mar 2023 |
§6.2 |
Euler's Theorem, subdivision, k-connectivity
hw7.pdf hw7.tex |
| Week 9 | ||
| L 15 Mon, 13 Mar 2023 |
§6.2 | Kuratowski's theorem |
| L 16 Wed, 15 Mar 2023 |
§6.3 |
QUIZ 4 (on HW 6)
PROJECT PROPOSAL DUE Coloring planar graphs: 5-color Theorem (using Kempe-chains) hw8.pdf (Not graded--do not turn in) hw8.tex |
| Week 10 | ||
| Mon, 20 Mar 2023 | SPRING | |
| Wed, 22 Mar 2023 | BREAK | |
| Week 11 | ||
| L 17 Mon, 27 Mar 2023 |
§? | ? |
| L 18 Wed, 29 Mar 2023 |
||
| Week 11 | ||
| L 19 Mon, 3 Apr 2023 |
||
| L 20 Wed, 5 Apr 2023 |
QUIZ 5 (HW 7 and 8) | |
| Week 12 | ||
| L 21 Mon, 10 Apr 2023 |
||
| L 22 Wed, 12 Apr 2023 |
||
| Week 13 | ||
| Mon, 17 Apr 2023 | HOLIDAY (Patriot's Day) | |
| L 23 Wed, 19 Apr 2023 |
||
| L 24 Fri, 21 Apr 2023 |
||
| Week 14 | ||
| L 25 Mon, 24 Apr 2023 |
||
| Wed, 26 Apr 2023 | EXAM 2 ?? (Note: not cumulative) | |
| Fri, 28 Apr 2023 | PROJECT DUE: report.pdf and slides.pdf | |
| Week 15 | ||
| Mon, 1 May 2023 |
Last day of class
PROJECT presentations 6:00-8:00pm |
|
| Week 16 | ||
| No Final Exam Yay! | ||
Academic Support at the StAAR Center:
The StAAR Center (formerly the Academic Resource Center and Student Accessibility Services) offers a variety of resources to all students (both undergraduate and graduate) in the Schools of Arts and Science, Engineering, the SMFA and Fletcher; services are free to all enrolled students. Students may make an appointment to work on any writing-related project or assignment, attend subject tutoring in a variety of disciplines, or meet with an academic coach to hone fundamental academic skills like time management or overcoming procrastination. Students can make an appointment for any of these services by visiting the StAAR Center (Links to an external site.)website, which can be accessed by the URL of
Mental Health Support:
As a student, there may be times when personal stressors or emotional difficulties interfere with your academic performance or well-being. The Counseling and Mental Health Service (CMHS) provides confidential consultation, brief counseling, and urgent care at no cost for all Tufts undergraduates as well as for graduate students who have paid the student health fee. To make an appointment, call 617-627-3360. Please visit the CMHS website: http://go.tufts.edu/Counseling (Links to an external site.) to learn more about their services and resources.