A reminder: this is today.
---------------------------
On 2024-12-02 13:36, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 5 December, given by Orestis Milolidakis. Please find the talk details below.
Best regards, Misha Tyomkyn.
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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz