VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

263-4513-00L 5 Credits DR , MSC D-MATH , D-INFK

Structural Graph Theory

Lecturers & Examiners: Dr. Raphael Mario Steiner
VVZ CR 4.8

Last Updated: 2026-02-05 16:30:06

Abstract

Structural graph theory forms, besides extremal graph theory, one of the two main pillars of modern graph theory. While the latter is concerned with maximizing the number of edges or the density of graphs, structural graph theory focuses on understanding the structural nature of all members of a class of graphs.This course will cover several cornerstone results of structural graph theory.

Objective

The students obtain a thorough understanding of the mathematical tools, techniques and results in structural graph theory, and understand the relations and applications which this rich theory has in other areas, such as computational complexity and logic. Additionally, they enhance their skillset for the design of efficient algorithms on structurally constrained classes of graphs.

Content

Graph minors: Connectivity and versions of Menger's theorem, Planar graphs, Wagner's theorem, Tree-width, algorithmic applications of tree-width and Courcelle's theorem, balanced separators and Alon-Seymour-Thomas theorem, Grid Minor Theorem, Erdős–Pósa property and algorithmic applications, Graph Minor Structure Theorem, Membership complexity, Wagner's conjecture Perfect graphs: Introduction to graph coloring and definition, Proof of the weak perfect graph theorem, Strong perfect graph theorem Hadwiger's conjecture: 4-Color-Theorem and precise results, Extremal density of graphs excluding a fixed minor, Recent advances

Resources

Lecture Notes

Will be provided well before the start of the HS.

Literature

Topics in Structural Graph Theory (Lowell W. Beineke, Robin J. Wilson) (Remark: Not a perfect fit for this course, but there is substantial overlap on some of the topics).

General Information

Language
English
Levels
DR , MSC
Frequency
Yearly recurring

Examination

Type
session examination
Mode
oral 20 minutes
The candidate gets questions and 5 minutes of preparation time. Afterwards, the oral exam takes 20 minutes.

Course Components

Type Title Time & Place Hours
lecture Structural Graph Theory
  • Tue 10:15-12:00 (LEE D 101)
2 h weekly
independent project Structural Graph Theory No time listed 2 h weekly

Offered In