Structural and algorithmic aspects of partial orderings of graphs

Tematyka rozprawy należy do teorii grafów. Głównym tematem rozprawy są twierdzenia opisujące grafy z zabronioną podstrukturą i ich zastosowania. Rozważamy zastosowania takich twierdzeń do teorii dobrego uporządkowania. W szczególności, korzystając z twierdzeń strukturalnych, wskazujemy kilka dobrze uporządkowanych podklas ze względu na różne porządki. Zajmujemy się rownież badaniem relacji pomiędzy niezmiennikami w kontekście problemów pokrywania i pakowania różnych struktur kombinatorycznych. W rozprawie opisujemy rownież algorytmiczne konsekwencje naszych wyników.

This thesis falls within the field of Graph Theory. A central theme is the study of exclusion theorems and their uses in related topics. One of them is well-quasi-ordering: we identify well-quasi-ordered subclasses for several orderings of graphs using structural decompositions. A second one the the study of the relations between combinatorial invariants related to problems of packing and covering of combinatorial structures. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results.