On Switching to H‐Free Graphs
Eva Jelínková, Jan Kratochvı́l · Journal of Graph Theory · 2013
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.