Abstrakt
We study the problem of deciding if, for a fixed graph H, a given graph is switching-equivalent to an H-free graph. In all cases of H that have been solved so far, the problem is decidable in polynomial time.
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)].