Unit:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)Πληροφορική
Author:
Chaniotis Aristotelis
Supervisors info:
Αρχοντία Γιαννοπούλου, Επίκουρη Καθηγήτρια, Τμήμα Πληροφορικής, ΕΚΠΑ
Δημήτριος Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής, ΕΚΠΑ
Original Title:
Structural and Topological Graph Theory and Well-Quasi-Ordering
Translated title:
Structural and Topological Graph Theory and Well-Quasi-Ordering
Summary:
In their Graph Minors series, Neil Robertson and Paul Seymour among other great results
proved Wagner's conjecture which is today known as the Robertson and Seymour's theorem.
In every step along their way to the final proof, each special case of the conjecture which they were proving
was a consequence of a "structure theorem", that sufficiently general graphs contain
minors or other sub-objects that are useful for the proof - or equivalently,
that graphs that do not contain a useful minor have a certain restricted structure, deducing that way also a useful information for the proof.
The main object of this thesis is the presentation of -relatively short-
proofs of several Robertson and Seymour's theorem's special cases, illustrating by this way the interplay between
structural graph theory and graphs' well-quasi-ordering.
We present also the proof of the perhaps most important special case of the Robertson and Seymour's theorem
which states that embeddability in any fixed surface can be characterized by forbidding finitely many minors.
The later result is deduced as a well-quasi-ordering result,
indicating by this way the interplay among topological graph theory and well-quasi-ordering theory.
Finally, we survey results regarding the well-quasi-ordering of graphs by other than the minor graphs' relations.
Main subject category:
Science
Keywords:
graph theory, graph minors, structural graph theory, topological graph theory, robertson, seymour, well-quasi-ordering, well-quasi-orders
Number of references:
125
