Charles Explorer logo
🇬🇧

On Switching to H-Free Graphs

Publication at Faculty of Mathematics and Physics |
2008

Abstract

In this paper we study the problem of deciding if, for a fixed graph H, a given graph is switching-equivalent to an H-free graph. We show that for H isomorphic to a claw, the problem is polynomial.

Further, we give a characterization of graphs switching-equivalent to a $K_{1,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.