A graph H is said to be an induced minor of another graph G “if a graph isomorphic to H can be [constructed] from G by a sequence of vertex deletions and edge contractions.”

The main theme of the paper is the complexity of graph isomorphism on graphs “characterized by one forbidden induced minor.” In the initial result, for a complete graph H, graph isomorphism for H-induced-minor-free graphs (that is, “no induced minor of G is isomorphic to H”) can be solved in polynomial time. The authors also prove a necessary and sufficient condition for an H-induced-minor-free graph to have bounded clique-width: the order of H is less than or equal to four. If H is an induced subgraph of P₄, then “graph isomorphism for H-induced-minor-free graphs can be solved in linear time.”

The core part of the study deals with “graph classes characterized by a forbidden induced minor H that has at most five vertices.” A GI-complete problem is “polynomial-time tractable or polynomial-time equivalent to the general problem.”

The first main theorem of the paper establishes that the graph isomorphism problem for (K₃∪K₁)-induced-minor-free graphs is GI-complete. It is also proves that such graphs do not have bounded clique-width. Following this result, the authors also prove that “the graph isomorphism problem can be solved in polynomial time on gem-induced-minor-free graphs,” and for an induced subgraph H of the gem graph, “the H-induced-minor-free graphs have bounded clique-width.”

The third main result states that the graph isomorphism problem for co-(P₃∪2K₁)-induced-minor-free graphs can be solved in polynomial time. For an induced subgraph H of co-(P₃∪2K₁), “the H-induced-minor-free graphs have bounded clique-width.” Furthermore, for a non-complete graph H of order at most five, “the graph isomorphism for H-induced-minor-free graphs is polynomial-time solvable if H is an induced subgraph of co-(P₃∪2K₁) or the gem; otherwise, it is GI-complete.”

In the last part of the paper, the authors show that for a non-complete graph H with at least six vertices, “graph isomorphism for the H-induced-minor-free graphs is GI-complete” and “H-induced-minor-free graphs have unbounded clique-width.”

The content is beautifully presented and the results and their proofs include nice structural analyses of the graphs concerned. The intended audience is the graph theory research community, including research scholars, professors, and postgraduate students. I would recommend the paper, as the content is innovative and interesting. It is very good work as well.