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

Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ 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₇-free graphs and in polynomial time for P₈-free graphs. In this paper, we solve it in polynomial time for P₉-free graphs.