Back to search

National and Kapodistrian University of Athens

Splittability within minor-closed classes to graphs of low maximum degree

Abstract

dc:description

Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K5 ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K5 ως έλασσον μέγιστου βαθμού 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(K5).

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Μηλολιδάκης Ορέστης
  • Milolidakis Orestis

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:5306609

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Μηλολιδάκης Ορέστης; Milolidakis Orestis. Splittability within minor-closed classes to graphs of low maximum degree. 2025. https://pergamos.lib.uoa.gr/uoa/dl/object/5306609