Maximum degree in minor-closed classes
Orestis Milolidakis
University of Athens and National Technical university of Athens
December 5, 2024, 12:20 in S6
Abstract
It is easy to see that every planar graph is a minor of another planar graph of maximum degree 3. Georgakopoulos proved that every finite $K_5$-minor free graph is a minor of another $K_5$-minor-free graph of maximum degree 22, and inquired what is the lowest possible value for this number.
This motivates the following generalization: Let $C$ be a minor-closed class. What is the minimum $k$ such that any graph in $C$ is a minor of a graph in $C$ of maximum degree $k$? Denote the minimum by $Δ(C)$.
We explore the value of $Δ(C)$ for various minor closed classes, and eventually show that a minor-closed class $C$ excludes an apex graph if and only if there exists a proper minor-closed superclass $C'$ of $C$ with $Δ(C')=3$. These results comprise the speaker's master's thesis.