Seminar on Graph Theory

Content

Schedule. Friday 15:15-17:00.

Organiser. Linda Cook

Important. Please contact Linda Cook with your interests and background!

1. Overview. Does it have to be true that at least three people at a party all know each other or all don’t know each other? What is the minimum number of rooms a the math department needs to make sure every course has a room assignment? If you draw a map how many colors do you need to ensure that adjacent countries receive distinct colors. Each of these problems can be understood using graph theory.

A graph is a combinatorial object consisting of a set of vertices and pairs of vertices called edges. While graph theory finds diverse applications in network science when objects are abstracted to be vertices and relations between them are represented by edges, in this course we will study the mathematical theory of graphs. Graph coloring will be a special focus of the seminar.

2. Content. The content of this course will ultimately depend on the students interest, but the following is a list of possible topics:

• Connectivity, Matchings, combinatorial duality theorems
• Coloring: Brook’s theorem, Vizing’s Theorem, Hadwidger’s conjecture
• Planar Graphs, the four color theorem, Kuratowski, Wagner
• Network Flows: Integer and group-valued flows, the 6-flow theorem
• Extremal graph theory and probabilistic methods: Ramsey’s theorem, Turan’s theorem, lower bounds for Ramsey numbers
• Topological Methods, The chromatic number of Kneser graphs
• Graph Minors: (Robertson-Seymour Graph Minor theory, Hadwidger’s conjecture), Planar graphs
• Induced subgraphs: Perfect graphs, Erdos-Hajnal Conjecture, Chi-Boundedness
• Related algorithms.

More advanced topics can be included, depending on the background and interest of the students.

3. Material
3.1 Prerequisites. We do not require students to have taken a prior course in discrete mathematics. A good background in proof-based mathematics, particularly induction, the basics of linear algebra and probability theory.

3.2 References. Here is a (non-comprehensive) list of references that may be used for the course:

1. Diestel, R., 2025. Graph theory (Vol. 173). Springer Nature.
2. Bondy, A, Murty, USR. Graph Theory, 2008 Springer.
3. Alon, Noga, and Joel H. Spencer. The probabilistic method. John Wiley & Sons, 2016.
4. Ziegler, Günter M., and Karl H. Hofmann. Proofs from the Book. Springer, 2006.

• Participation (presentation(s) and participation in lectures): 40%.
• Homework (preparing problem sets, hand-in homework and typed up notes): 60%.

1. convert material from part of a graduate-level textbook or scientific paper into a coherent and comprehensible presentation for fellow students and mathematicians in general;
2. choose appropriate means of communicating theoretical mathematics to fellow students and mathematicians, in written and oral form;
3. formulate and correct exercises that maintain a balance between relevance, interest, and feasibility;
4. explain specific topics from the content list of the seminar to fellow students, and put them into context as far as their relevance to wider mathematics is concerned.

• Presentation(s) = presentation(s) and participation in lectures.
• Homework = combined output for homework assignments (preparing problem sets, hand-in homework and typed up notes).