Αναζητώντας παρεμποδίσεις k-απόγειων γραφημάτων για κλάσεις με φραγμένο βαθμό

Abstract

Θα αντιμετωπίσουμε προβλήματα που αφορούν την αναζήτηση παρεμποδίσεων κλάσεων γραφημάτων. Οι παρεμποδίσεις μιας κλάσης ορίζονται ως τα ελαχιστοτικά, ως προς τη σχέση του ελάσσονος, γραφήματα που δεν ανήκουν σε μια κλάση γραφημάτων κλειστή ως προς ελάσσονα. Η συνεισφορά της εργασίας μας μπορεί να χωριστεί σε 2 μέρη. ́Ενα περισσότερο θεωρητικό, που περιλαμβάνει την απόδειξη ενός τετραγωνικού (ως προς k και d) φράγματος για το μέγεθος των παρεμποδίσεων των k-απόγειων της κλάσης των γραφημάτων με μέγιστο βαθμό μικρότερο από d, αλλά και ενός φράγματος για την ειδική περίπτωση d = 2. Ακόμα, υπάρχει ένα μέρος περισσότερο πρακτικό, που συνίσταται στην εύρεση και παρουσίαση των παρεμποδίσεων 4 κλάσεων, εκ των οποίων οι 3 είναι k-απόγεια των γραφημάτων με μέγιστο βαθμό μικρότερο από d, για τα 3 ζεύγη τιμών των (k, d), (1,2),(2,2) και (1,3). Η τέταρτη κλάση είναι μια υποκλάση της τρίτης, που εισάγει τον περιορισμό της ακυκλικότητας.