{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:5306609"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:5306609","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Splittability within minor-closed classes to graphs of low maximum degree","abstract":"Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K$_5$ ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K$_5$ ως έλασσον μέγιστου βαθμού 22, και ρώτησε αν αυτός είναι ο ελάχιστος δυνατόν. Αυτό παρακινεί την εξής γενίκευση. Έστω $C$ μία κλάση κλειστή υπό ελάσσονα. Ποιο είναι το ελάχιστο $k$ έτσι ώστε οποιοδήποτε γράφημα της $C$ είναι έλασον ενός γραφήματος της $C$ μέγιστου βαθμού $k$; Συμβολίζουμε το ελάχιστο με $Δ(C)$ και θέτουμε την τιμή του σε $\\infty$ εάν δεν υπάρχει τέτοιο $k$. Εξερευνούμε την τιμή του $Δ(C)$ για ποικίλες κλάσεις κλειστές υπό ελάσσονα και τελικά αποδεικνύουμε ότι μια κλάση κλειστή υπό ελάσσονα $C$ αποκλείει ένα απόγειο γράφημα ως έλασσον εάν και μόνο εάν υπάρχει μια κλειστή υπό ελάσσονα υπερκλάση $C'$ της $C$ με $Δ(C')=3$ εάν και μόνο εάν υπ άρχει κλειστή υπό ελάσσονα υπερκλάση $C'$ με πεπερασμένο $Δ(C')$. Αυτό επαυξάνει μια λίστα με 5 άλλους χαρακτηρισμούς των κλάσεων κλειστών υπό ελάσσονα που αποκλείουν ένα απόγειο γράφημα από τους Dujmovic, Morin και Wood. Επιπλέον, επεκτείνουμε και απλοποιούμε το αποτέλεσμα των Markov και Shi ότι δεν έχει κάθε γράφημα δενδροπλάτους $\\leq$ k διάσπαση μέγιστου βαθμού 3 και δενδροπλάτους $\\leq k$. Τέλος, απλοποιούμε την απόδειξη του Γεωργακόπουλου για την ύπαρξη ενός αριθμίσιμα άπειρου καθολικού γραφήματος για την $Forb(K_5)$.","abstract_html":"Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K<span class=\"etd-inline-math\"><sub>5</sub></span> ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K<span class=\"etd-inline-math\"><sub>5</sub></span> ως έλασσον μέγιστου βαθμού 22, και ρώτησε αν αυτός είναι ο ελάχιστος δυνατόν. Αυτό παρακινεί την εξής γενίκευση. Έστω $C$ μία κλάση κλειστή υπό ελάσσονα. Ποιο είναι το ελάχιστο $k$ έτσι ώστε οποιοδήποτε γράφημα της $C$ είναι έλασον ενός γραφήματος της $C$ μέγιστου βαθμού $k$; Συμβολίζουμε το ελάχιστο με $Δ(C)$ και θέτουμε την τιμή του σε $\\infty$ εάν δεν υπάρχει τέτοιο $k$. Εξερευνούμε την τιμή του $Δ(C)$ για ποικίλες κλάσεις κλειστές υπό ελάσσονα και τελικά αποδεικνύουμε ότι μια κλάση κλειστή υπό ελάσσονα $C$ αποκλείει ένα απόγειο γράφημα ως έλασσον εάν και μόνο εάν υπάρχει μια κλειστή υπό ελάσσονα υπερκλάση $C&#x27;$ της $C$ με $Δ(C&#x27;)=3$ εάν και μόνο εάν υπ άρχει κλειστή υπό ελάσσονα υπερκλάση $C&#x27;$ με πεπερασμένο $Δ(C&#x27;)$. Αυτό επαυξάνει μια λίστα με 5 άλλους χαρακτηρισμούς των κλάσεων κλειστών υπό ελάσσονα που αποκλείουν ένα απόγειο γράφημα από τους Dujmovic, Morin και Wood. Επιπλέον, επεκτείνουμε και απλοποιούμε το αποτέλεσμα των Markov και Shi ότι δεν έχει κάθε γράφημα δενδροπλάτους $\\leq$ k διάσπαση μέγιστου βαθμού 3 και δενδροπλάτους $\\leq k$. Τέλος, απλοποιούμε την απόδειξη του Γεωργακόπουλου για την ύπαρξη ενός αριθμίσιμα άπειρου καθολικού γραφήματος για την <span class=\"etd-inline-math\">Forb(K<sub>5</sub>)</span>.","abstract_has_math":true,"creators":["Μηλολιδάκης Ορέστης","Milolidakis Orestis"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025","date_published":"2025","updated_at":"2026-11-19T06:40:15Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5306609"],"render_values":[{"text":"uoadl:5306609","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5306609","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5306609","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A5306609","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Μηλολιδάκης Ορέστης","Milolidakis Orestis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5306609","https://pergamos.lib.uoa.gr/uoa/dl/object/5306609"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K$_5$ ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K$_5$ ως έλασσον μέγιστου βαθμού 22, και ρώτησε αν αυτός είναι ο ελάχιστος δυνατόν. Αυτό παρακινεί την εξής γενίκευση. Έστω $C$ μία κλάση κλειστή υπό ελάσσονα. Ποιο είναι το ελάχιστο $k$ έτσι ώστε οποιοδήποτε γράφημα της $C$ είναι έλασον ενός γραφήματος της $C$ μέγιστου βαθμού $k$; Συμβολίζουμε το ελάχιστο με $Δ(C)$ και θέτουμε την τιμή του σε $\\infty$ εάν δεν υπάρχει τέτοιο $k$. Εξερευνούμε την τιμή του $Δ(C)$ για ποικίλες κλάσεις κλειστές υπό ελάσσονα και τελικά αποδεικνύουμε ότι μια κλάση κλειστή υπό ελάσσονα $C$ αποκλείει ένα απόγειο γράφημα ως έλασσον εάν και μόνο εάν υπάρχει μια κλειστή υπό ελάσσονα υπερκλάση $C'$ της $C$ με $Δ(C')=3$ εάν και μόνο εάν υπ άρχει κλειστή υπό ελάσσονα υπερκλάση $C'$ με πεπερασμένο $Δ(C')$. Αυτό επαυξάνει μια λίστα με 5 άλλους χαρακτηρισμούς των κλάσεων κλειστών υπό ελάσσονα που αποκλείουν ένα απόγειο γράφημα από τους Dujmovic, Morin και Wood. Επιπλέον, επεκτείνουμε και απλοποιούμε το αποτέλεσμα των Markov και Shi ότι δεν έχει κάθε γράφημα δενδροπλάτους $\\leq$ k διάσπαση μέγιστου βαθμού 3 και δενδροπλάτους $\\leq k$. Τέλος, απλοποιούμε την απόδειξη του Γεωργακόπουλου για την ύπαρξη ενός αριθμίσιμα άπειρου καθολικού γραφήματος για την $Forb(K_5)$.","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 if this is smallest possible. 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)$ and set it to be $\\infty$ if no such $k$ exists. We explore the value of $Δ(C)$ for various minor closed classes, and eventually prove 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$ if and only if there exists a proper minor-closed superclass $C'$ of $C$ with finite $Δ(C')$. This complements a list of 5 other characterizations of the minor-closed classes excluding an apex graph by Dujmovic, Morin and Wood. Furthermore, we extend and simplify Markov and Shi's result that not every graph of treewidth $\\leq$ k has a degree 3 expansion of treewidth $\\leq k$. Finally, we simplify Georgakopoulos' proof on the existence of a countable universal graph of $Forb(K_5)$."]},{"key":"dc:title","label":"Title","values":["Splittability within minor-closed classes to graphs of low maximum degree"]}]}],"canonical_facts":{"dc:creator":["Μηλολιδάκης Ορέστης","Milolidakis Orestis"],"dc:date":["2025"],"dc:description":["Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K$_5$ ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K$_5$ ως έλασσον μέγιστου βαθμού 22, και ρώτησε αν αυτός είναι ο ελάχιστος δυνατόν. Αυτό παρακινεί την εξής γενίκευση. Έστω $C$ μία κλάση κλειστή υπό ελάσσονα. Ποιο είναι το ελάχιστο $k$ έτσι ώστε οποιοδήποτε γράφημα της $C$ είναι έλασον ενός γραφήματος της $C$ μέγιστου βαθμού $k$; Συμβολίζουμε το ελάχιστο με $Δ(C)$ και θέτουμε την τιμή του σε $\\infty$ εάν δεν υπάρχει τέτοιο $k$. Εξερευνούμε την τιμή του $Δ(C)$ για ποικίλες κλάσεις κλειστές υπό ελάσσονα και τελικά αποδεικνύουμε ότι μια κλάση κλειστή υπό ελάσσονα $C$ αποκλείει ένα απόγειο γράφημα ως έλασσον εάν και μόνο εάν υπάρχει μια κλειστή υπό ελάσσονα υπερκλάση $C'$ της $C$ με $Δ(C')=3$ εάν και μόνο εάν υπ άρχει κλειστή υπό ελάσσονα υπερκλάση $C'$ με πεπερασμένο $Δ(C')$. Αυτό επαυξάνει μια λίστα με 5 άλλους χαρακτηρισμούς των κλάσεων κλειστών υπό ελάσσονα που αποκλείουν ένα απόγειο γράφημα από τους Dujmovic, Morin και Wood. Επιπλέον, επεκτείνουμε και απλοποιούμε το αποτέλεσμα των Markov και Shi ότι δεν έχει κάθε γράφημα δενδροπλάτους $\\leq$ k διάσπαση μέγιστου βαθμού 3 και δενδροπλάτους $\\leq k$. Τέλος, απλοποιούμε την απόδειξη του Γεωργακόπουλου για την ύπαρξη ενός αριθμίσιμα άπειρου καθολικού γραφήματος για την $Forb(K_5)$.","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 if this is smallest possible. 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)$ and set it to be $\\infty$ if no such $k$ exists. We explore the value of $Δ(C)$ for various minor closed classes, and eventually prove 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$ if and only if there exists a proper minor-closed superclass $C'$ of $C$ with finite $Δ(C')$. This complements a list of 5 other characterizations of the minor-closed classes excluding an apex graph by Dujmovic, Morin and Wood. Furthermore, we extend and simplify Markov and Shi's result that not every graph of treewidth $\\leq$ k has a degree 3 expansion of treewidth $\\leq k$. Finally, we simplify Georgakopoulos' proof on the existence of a countable universal graph of $Forb(K_5)$."],"dc:identifier":["uoadl:5306609","https://pergamos.lib.uoa.gr/uoa/dl/object/5306609"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Splittability within minor-closed classes to graphs of low maximum degree"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T06:40:15Z"}