Graph classes defined by ordered forbidden structures

Celem pracy jest scharakteryzowanie klas grafów, które można zdefiniować za pomocą małych struktur zabronionych. W rozdziale 1 przedstawiamy podstawowe definicje i własności klas grafów definiowanych przez struktury zabronione. W rozdziale 2 charakteryzujemy wszystkie klasy grafów definiowanych przez jedną strukturę zabronioną wielkości trzy; wśród tych klas grafów odnajdujemy grafy porównywalności i nieporównywalności, grafy cięciwowe i dopełnienia grafów cięciwowych, grafy bez kliki wielkości trzy, i grafy bez zbioru niezależnego wielkości trzy. W rozdziale 3 charakteryzujemy wszystkie klasy grafów definiowanych przez dwie struktury wielkości trzy: wśród tych klas grafów znajdują się grafy progowe, permutacji, dwudzielne, przedziałowe i równoprzedziałowe, split grafy, itd. W ostatnim rozdziale 4 przedstawiamy przykłady klas grafów, które można zdefiniować za pomocą struktur zabronionych wielkości cztery.The topic of this thesis is characteristic of graph classes, that are definable by small forbidden structures. In the first chapter we introduce basic definitions and properties of graph classes definable by small forbidden structures. In chapter 2 we characterize all graph classes which are defined by single forbidden structure of size 3; we can find among them comparability and incomparability graphs, chordal graphs and chordal graph complement, graphs without clique of size 3 and graphs without independent set of size 3. In chapter 3 we characterize all graphs defined by two forbidden structures of size 3; among them we can find threshold, permutation, bipartite, interval and unit interval graphs etc. In the final chapter 4 we introduce examples of graph classes, that can be defined by forbidden structures of size 4