Ο φοιτητής του προγράμματος Ορέστης Μηλολιδάκης θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Splittability in minor-closed classes to graphs of bounded maximum degree
την Παρασκευή 21 Μαρτίου 2025 και ώρα 11:30, μέσω webex (https://centralntua.webex.com/centralntua/j.php?MTID=m4a0eff7a26a9e4407b0f6d5e6e1f515a).
Σύνοψη Διπλωματικής:
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$.
Η Επιτροπή:
Δημήτρης Αχλιόπτας,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών Ε.Κ.Π.Α.
Άγγελος Γεωργακόπουλος (Συνεπιβλέπων),
Εξωτερικός Συνεργάτης, ΑΛΜΑ
Αρχοντία Χ. Γιαννοπούλου,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών Ε.Κ.Π.Α.
Άρης Παγουρτζής (Συνεπιβλέπων),
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Ε.Μ.Π.