On Switching to H‐Free Graphs |
| |
Authors: | Eva Jelínková Jan Kratochvíl |
| |
Institution: | 1. DEPARTMENT OF APPLIED MATHEMATICS CHARLES UNIVERSITY, MALOSTRANSKé NáM. 25, 118 2. 00 PRAHA, CZECH REPUBLIC |
| |
Abstract: | In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P4. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K1, 2‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees. |
| |
Keywords: | Seidel's switching computational complexity H‐free graphs |
|
|