Χρωματισμοί, εμφυτεύσεις και συναφή γραφοθεωρητικά προβλήματα
Authors: Ραυτοπούλου Χρυσάνθη 
Published: September 2021

Οι εμφυτεύσεις γραφημάτων σε βιβλίο είναι ένα ευρέως μελετημένο κεφάλαιο τις θεωρίας γραφημάτων με πολλές εφαρμογές. Η σχετική ερευνητική δραστηριότητα χρονολογείται από τις αρχές της δεκαετίας του 70 και έχει παράξει πλούσια βιβλιογραφία. Στην παρούσα διδακτορική διατριβή εστιάζουμε σε δύο συγκεκριμένα προβλήματα. Το πρώτο τέθηκε από τον Heath: έδειξε ότι τα επίπεδα γραφήματα μέγιστου βαθμού 3 είναι υποχαμιλτονιανά και συνεπώς εμφυτεύονται σε βιβλίο με 2 σελίδες, και έθεσε το ερώτημα εάν το ίδιο ισχύει για επίπεδα γράφημα με μέγιστο βαθμό μεγαλύτερο του 3. Προς αυτή την κατεύθυνση, αποδεικνύουμε ότι όλα τα επίπεδα γραφήματα μέγιστου βαθμού 4 είναι πράγματι υποχαμιλτονιανά. Το δεύτερο πρόβλημα σχετίζεται με το πάχος εμφύτευσης σε βιβλίο γραφημάτων που δεν είναι κλειστά υπό ελάσσονα. Είναι γνωστό ότι εάν ένα γράφημα είναι κλειστό υπό ελάσσονα, τότε το πάχος εμφύτευσής του σε βιβλίο είναι φραγμένο. Ωστόσο, παρέμενε ανοιχτό εάν υπάρχει κάποιο φράγμα για οικογένειες γραφημάτων που δεν είναι κλειστές υπό ελάσσονα. Αποδεικνύουμε ότι η οικογένεια των 1-επίπεδων γραφημάτων, δηλαδή των γραφημάτων που μπορούν να απεικονιστούν στο επίπεδο έτσι ώστε κάθε ακμή να τέμνεται το πολύ μία φορά, έχουν φραγμένο πάχος εμφύτευσης σε βιβλίο. Απ' όσο γνωρίζουμε, αυτή είναι η πρώτη απόπειρα προσδιορισμού κάποιου άνω φράγματος για το πάχος εμφύτευσης σε βιβλίο τέτοιων οικογενειών γραφημάτων. Ένα άλλο θέμα της θεωρίας γραφημάτων στο οποίο εστιάζουμε, είναι μία παραλλαγή του γνωστού προβλήματος ολικών χρωματισμών γραφημάτων. Εξετάζουμε ολικούς χρωματισμούς που διαχωρίζουν γειτονικές κορυφές βάση του συνόλου των χρωμάτων που χρησιμοποιούνται για την κορυφή και τις προσκείμενες ακμές της. Το πρόβλημα αυτό προτάθηκε από τον Καθηγητή B\'ela Bollob\'as. Βασικά πρότεινε να εξετάσουμε AVD-ολικούς χρωματισμούς γραφημάτων με μέγιστο βαθμό 3, προκειμένου να απαντηθεί ένα ερώτημα που τέθηκε από τον Hulgan και αφορά εάν 5 χρώματα επαρκούν για αυτόν το χρωματισμό ή απαιτούνται 6 χρώματα για ορισμένα 3-κανονικά γραφήματα. Αν και δεν καταφέραμε να απαντήσουμε συνολικά την ερώτηση αυτή, δείξαμε ότι 5 χρώματα επαρκούν για τα γενικευμένα Halin γραφήματα με μέγιστο βαθμό 3. Αυτό είναι επίσης ένα βήμα προς τον πλήρη προσδιορισμό του AVD-ολικού χρωματικού αριθμού των επίπεδων γραφημάτων. Από μία άλλη οπτική γωνία, δείξαμε επίσης ότι η εικασία των AVD-ολικών χρωματισμών ισχύει για 4-κανονικά γραφήματα. Στην παρούσα διδακτορική διατριβή, μελετήσαμε και ορισμένα προβλήματα της απεικόνισης γραφημάτων. Ειδικότερα, απαντάμε μία εικασία που διατυπώθηκε από τον Lov\'asz σχετικά με αναπαραστάσεις με κύκλους των 4-κανονικών επίπεδων γραφημάτων. Οι αναπαραστάσεις με κύκλους σχετίζονται με το γνωστό πρόβλημα αναπαράστασης γραφημάτων ως γραφήματα επαφών. Αποδεικνύουμε ότι εάν το γράφημα είναι τρισυνεκτικό, τότε τεχνικές συσκευασίας κύκλων μπορούν να χρησιμοποιηθούν για την κατασκευή μίας πραγματοποίησης ως ένα σύστημα εφαπτόμενων κύκλων. Ωστόσο, εάν το γράφημα δεν είναι τρισυνεκτικό υπάρχουν άπειρα αντιπαραδείγματα. Επίσης, παρουσιάζουμε καινούρια αποτελέσματα για άριστες ομαλές ορθογώνιες απεικονίσεις, οι οποίες εισήχθησαν πρόσφατα στην βιβλιογραφία της απεικόνισης γραφημάτων, και επεκτείνουμε και βελτιώνουμε προηγούμενα αποτελέσματα πάνω στο συγκεκριμένο πρόβλημα.