Graph Theory (그래프이론)

Class Info

Class Number: MATH 848-001
Dates: Mar 02 2021 - Jun 17 2021
Room: NS 313-3
Meeting time:

Mon 10:30 - 11:50 (2B)

Wed 15:00 - 16:20 (7A)

Prof: Mark Siggers
Office Hours
Text: We will use these class notes.
Other references: Diestal's "Graph Theory" and Devos' Class Notes.

Links

Class Info

Students in Quarantine

Note that the Tuesday class has moved to Monday.

On the Class Info linked on the right you will find what we have covered and links to videos of when I taught this class last year.

We will try to Zoom or to Nextcloud talk the class. I will send you a link via whatsapp just before the class is scheduled to begin.

Syllabus

Usually, we will spend about a week (one class) on each of the following topics. The emphasise of the class is usually proof techniques and writing.
However, our class consists solely of students not from the math department, having less experience in proof. We will take our time with basic proofs, learning slowly how to prove things. But we will likely omit or only sketch the more involved proofs. We will spend more time on computation (counting!) and trying to understand applications of graphs.
I am open to changing the topics below to graph topics that are more applied. If you have any applications of graphs (or networks) from your work, please feel free to suggest it to me as a topic.

Basics, Degree Sequences
Graph colouring, Brooks' Theorem
Eulerian and Hamiltonian Graphs
Trees
Connectivity and Menger's Theorem
Planarity and Kuratowski's Theorem
4-colour problem, List colouring, Thomassen's Five-list-colouring theorem.
Chordal Graphs and BFS
Graph Homomorphisms
Extremal Graph Theory, Turan's
Ramsey Theory and the Probabilistic Method

Grading

We will decide the grading once everybody can attend. This should be around the end of March. We will likely just do a midterm and final test. But if the class prefers, we can do it based on presentations and attendence/participation.