Computational complexity in Graph Theory

Seidel's switching is a graph operation , which for a given graph G and one of its vertices v gives the graph derived from G by replacing edges adjacent to v by non-edges and vice-versa. A graph H is called a switch of G, if H can be obtained from G by a sequence of switches of its vertices. In the thesis we introduce known results ab out computational complexity of problems if for a given graph G t here exists its switching lying in a given graph class (}. For different graph classes g, we later study a characterization of the class of all graphs, which can be switched into g, in terms of minimal forbidden induced subgraphs. We introduce a full characterization of a class of graphs switchable to a disjoint union af cutworms, respectively partial pairings by forbidden subgraphs. We also prove that a class of graphs switchable to chordal has infinit ely many non-isomorphic forbidden subgraphs. At the end we deal with the relationship between swit ching and other graph operations and graph classes operations