Σε αυτή τη διπλωματική εργασία, όλα τα γραφήματα είναι πεπερασμένα και μπορεί
να έχουν θηλιές και πολλαπλές ακμές. Έστωσαν uw και wv δύο ξεχωριστές γειτονικές ακμές σε ένα γράφημα G. Οι ακμές uw και wv καλούνται ανυψωμένες, όταν διαγράφονται από το G και προστίθεται μια νέα ακμή uv στη θέση τους. Λέγεται
ότι ένα γράφημα G περιέχει μια εμβύθιση H, όταν ένα γράφημα ισομορφικό με το
H μπορεί να σχηματιστεί από ένα υπογράφημα του G, ανυψώνοντας ζεύγη ακμών
(και αφαιρώντας απομονωμένες κορυφές).
Η κλασική εικασία του Hadwiger συσχετίζει την ύπαρξη της κλίκας ως έλασσον ενός γραφήματος G με τον χρωματικό αριθμό του χ(G). Ειδικότερα, η εικασία του Hadwiger υποδηλώνει ότι κάθε γράφημα χωρίς θηλιά και Kt-έλασσον είναι (t−1)-χρωματίσιμο, αποτελώντας μια ευρεία γενίκευση του Θεώρηματος Τεσσάρων Χρωμάτων. Η εικασία αυτή παραμένει ακόμη ως ένα από τα ανοιχτά προβλήματα στη Θεωρία των Γραφημάτων. Κατά συνέπεια, οι σχέσεις μεταξύ του χρωματικού αριθμού ενός γραφήματος G και του μεγαλύτερου μεγέθους ενός πλήρους γραφήματος που περιέχεται στο G προσέλκυσαν πολύ ενδιαφέρον. Όσον αφορά τις εμβυθίσεις, η εικασία των Abu-Khzam και Langston υποδηλώνει ότι το πλήρες γράφημα Kt μπορεί να εμβυθιστεί σε οποιοδήποτε t-χρωματίσιμο γράφημα.
Μια παραλλαγή της, που αφορά τον ελάχιστο βαθμό αντί για τον χρωματικό αριθμό, είναι η εξής: Έστω d(t) ο μικρότερος ακέραιος έτσι ώστε κάθε απλό γράφημα ελαχίστου βαθμού τουλάχιστον d(t) να περιέχει μια εμβύθιση Kt, τότε d(t) = t−1. Σε αυτή τη διπλωματική εργασία, αναλύεται η απόδειξη για τις τιμές t ∈ {5, 6, 7} (όπως αποδεικνύεται από τους DeVos, Kawarabayashi, Mohar και Okamura). Επιπλέον μελετάται η απόδειξη ότι η εικασία δεν αληθεύει όταν t ∈ {8, 9, 11} (όπως αποδεικνύεται από τις Collins και Heenean) καθώς και ένα αντιπαράδειγμα του Seymour για t = 10 που υποδεικνύει ότι d(t) ≥ t για τιμές t ≥ 10 διαψεύδοντας την εικασία. Τέλος, παρουσιάζονται δύο άνω φράγματα της συνάρτησης d(t), το πρώτο αφορά τις ισχυρές εμβυθίσεις όπου d(t) ≤ 200t και το δεύτερο σχετίζεται με τις ασθενείς εμβυθίσεις όπου δείχνεται ότι d(t) ≤ 7t + 7.
(EL)
In this thesis, all graphs are finite and may have loops and multiple edges. Let uw and wv be two distinct adjacent edges in a graph G. To lift the edges uw and wv, is to delete them from G and add a new edge uv. A graph G is said to contain an H-immersion, if a graph isomorphic to H can be obtained from a subgraph of G by lifting pairs of edges (and possibly removing isolated vertices).
The classical conjecture of Hadwiger relates the clique minor containment in a graph G and the chromatic number χ(G) of G. Hadwiger's conjecture states that every loopless graph without a Kt-minor is (t−1)-colourable, suggesting a far-reaching generalization of the Four-Colour Theorem. It remains one of the deepest open problems in Graph Theory. Consequently, relations between the chromatic number of a graph G and the largest size of a complete graph contained in G attracted a lot of interest. Regarding immersion, the conjecture of Abu-Khzam and Langston states that the graph Kt can be immersed in any t-chromatic graph.
A variant of this regards the minimum degree of a graph instead of the chromatic number as follows: Let d(t) be the smallest integer such that every simple graph of minimum degree at least d(t) contains an immersion of Kt, then d(t) = t − 1. In this thesis, we analyse the proof for the values t ∈ {5, 6, 7} (as proven by DeVos, Kawarabayashi, Mohar and Okamura). Furthermore, we study the reason the conjecture does not hold for t ∈ {8, 9, 11} along with a counterexample of Seymour for t = 10 resulting that d(t) ≥ t for t ≥ 10. Finally, two upper bounds are presented, one of the function d(t) regarding strong immersions showing that d(t) ≤ 200t and another one for weak immersions indicating that d(t) ≤ 7t + 7.
(EN)
/aggregator-openarchives/portal/institutions/uoa
