Finding Dominating Induced Matchings in P-9-Free Graphs in Polynomial Time

Let G = (V, E) be a finite undirected graph. An edge subset E ' subset of E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E '. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is -complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P-7-free graphs and in polynomial time for P-8-free graphs. In this paper, we solve it in polynomial time for P-9-free graphs.