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

Andreas Brandst¨dt a ∗

Raffaele Mosca †

April 2, 2020

## Abstract

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 NP -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.

Keywords : dominating induced matching; P 9 -free graphs; polynomial time algorithm.

## 1 Introduction

Let G = ( V, E ) be a finite simple undirected graph, i.e., an undirected graph without loops and multiple edges. Given an edge e ∈ E , we say that e dominates itself and every edge sharing a vertex with e . An edge subset M ⊆ E is an induced matching if the pairwise distance between its members is at least 2 (i.e., the distance property ), that is, M is isomorphic to kP 2 for k = | M | . A subset M ⊆ E is a dominating induced matching ( d.i.m. for short) of G if M is an induced matching in G such that every edge in E is dominated by exactly one edge in M . Clearly, not every graph G has a d.i.m.; the Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G .

The DIM problem is also called Efficient Edge Domination (EED) in various papers: Recall that a vertex v ∈ V dominates itself and its neighbors. A vertex subset D ⊆ V is an efficient dominating set ( e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex in D . The notion of efficient domination was introduced by Biggs [2] under the name perfect code . The Efficient Domination (ED) problem asks for the existence of an e.d.s. in a given graph G (note that not every graph has an e.d.s.) A set M of edges in a graph G is an efficient edge dominating set ( e.e.d.s. for short) of G if and only if it is an e.d.s. in its line graph L G ( ). The Efficient Edge Domination (EED) problem asks for the existence of an e.e.d.s. in a given graph G . Thus, the EED problem

∗ Institut f¨r u Informatik, Universit¨t a Rostock, A.-Einstein-Str. 22, D-18051 Rostock, Germany, a ndreas.brandstaedt@uni-rostock.de

† Dipartimento di Economia, Universit´ a degli Studi 'G. D'Annunzio' Pescara 65121, Italy. r .mosca@unich.it

for a graph G corresponds to the ED problem for its line graph L G ( ). Note that not every graph has an e.e.d.s.

In [10], it was shown that the DIM problem is NP -complete; see also [3, 9, 13, 14]. However, for various graph classes, DIM is solvable in polynomial time. For mentioning some examples, we need the following notions:

Let P k denote the chordless path P with k vertices, say a , . . . , a 1 k , and k -1 edges a a i i +1 , 1 ≤ i ≤ k -1; we also denote it as P = ( a , . . . , a 1 k ).

For indices i, j, k ≥ 0, let S i,j,k denote the graph H with vertices u, x 1 , . . . , x i , y , . . . , y 1 j , z , . . . , z 1 k such that the subgraph induced by u, x 1 , . . . , x i forms a P i +1 ( u, x 1 , . . . , x i ), the subgraph induced by u, y 1 , . . . , y j forms a P j +1 ( u, y 1 , . . . , y j ), and the subgraph induced by u, z 1 , . . . , z k forms a P k +1 ( u, z 1 , . . . , z k ), and there are no other edges in S i,j,k ; u is called the center of H . Thus, claw is S 1 1 1 , , , and P k is isomorphic to S k -1 0 0 , , .

For a set F of graphs, a graph G is called F -free if no induced subgraph of G is contained in F . If |F| = 1, say F = { H } , then instead of { H } -free, G is called H -free.

The following results are known:

Theorem 1. DIM is solvable in polynomial time for

- ( ) i S 1 1 1 , , -free graphs [ 9 , ]
- ( ii ) S 1 2 3 , , -free graphs [ 12 , ]
- ( iii ) S 2 2 2 , , -free graphs [ 11 , ]
- ( iv ) S 1 2 4 , , -free graphs [ 6 , ]
- ( v ) S 2 2 3 , , -free graphs [ 7 , ]
- ( vi ) S 1 1 5 , , -free graphs [ 8 , ]
- ( vii ) P 7 -free graphs [ 4 ] (in this case even in linear time),
- ( viii ) P 8 -free graphs [ 5 . ]

In [11], it is conjectured that for every fixed i, j, k , DIM is solvable in polynomial time for S i,j,k -free graphs (actually, an even stronger conjecture is mentioned in [11]); this includes P k -free graphs for k ≥ 9. In this paper we show that DIM can be solved in polynomial time for P 9 -free graphs (generalizing the corresponding results for P 7 -free and for P 8 -free graphs).

## 2 Definitions and Basic Properties

## 2.1 Basic notions

Let G be a finite undirected graph without loops and multiple edges. Let V ( G ) or V denote its vertex set and E G ( ) or E its edge set (say G = ( V, E )); let n = | V | and m = | E | . For v ∈ V , let N v ( ) := { u ∈ V : uv ∈ E } denote the open neighborhood of v , and let N v [ ] := N v ( ) ∪ { v } denote the closed neighborhood of v . If xy ∈ E , we also say that x and y see each other , and if xy ∈ E , we say that x and y miss each other . A

/negationslash

/negationslash

/negationslash vertex set S is independent in G if for every pair of vertices x, y ∈ S , xy ∈ E . A vertex set Q is a clique in G if for every pair of vertices x, y ∈ Q x , = y , xy ∈ E . For uv ∈ E let N uv ( ) := N u ( ) ∪ N v ( ) \ { u, v } and N uv [ ] := N u [ ] ∪ N v [ ].

For U ⊆ V , let G U [ ] denote the subgraph of G induced by vertex set U . Clearly xy ∈ E is an edge in G U [ ] exactly when x ∈ U and y ∈ U ; thus, G U [ ] can simply be denoted by U (if understandable).

For A ⊆ V and B ⊆ V , A ∩ B = ∅ , we say that A 0 © B ( A and B miss each other ) if there is no edge between A and B , and A and B see each other if there is at least one edge between A and B . If a vertex u / B ∈ has a neighbor v ∈ B then u contacts B . If every vertex in A sees every vertex in B , we denote it by A 1 © B . For A = { a } , we simply denote A 1 © B by a 1 © B , and correspondingly A 0 © B by a 0 © B . If for A ′ ⊆ A A , ′ 0 © ( A \ A ′ ), we say that A ′ is isolated in G A [ ]. For graphs H 1 , H 2 with disjoint vertex sets, H 1 + H 2 denotes the disjoint union of H 1 , H 2 , and for k ≥ 2, kH denotes the disjoint union of k copies of H . For example, 2 P 2 is the disjoint union of two edges.

As already mentioned, a chordless path P k , k ≥ 2, has k vertices, say v , . . . , v 1 k , and k -1 edges v v i i +1 , 1 ≤ i ≤ k -1; the length of P k is k -1. We also denote it as P = ( v , . . . , v 1 k ).

A chordless cycle C k , k ≥ 3, has k vertices, say v , . . . , v 1 k , and k edges v v i i +1 , 1 ≤ i ≤ k -1, and v v k 1 ; the length of C k is k .

Let K i , i ≥ 1, denote the clique with i vertices. Let K 4 -e or diamond be the graph with four vertices, say v , v 1 2 , v 3 , u , such that ( v , v 1 2 , v 3 ) forms a P 3 and u 1 ©{ v , v 1 2 , v 3 } ; its mid-edge is the edge uv 2 .

A butterfly has five vertices, say, v , v 1 2 , v 3 , v 4 , u , such that v , v 1 2 , v 3 , v 4 induce a 2 P 2 with edges v v 1 2 and v v 3 4 (the peripheral edges of the butterfly), and u 1 ©{ v , v 1 2 , v 3 , v 4 } .

/negationslash

/negationslash

We often consider an edge e = uv to be a set of two vertices; then it makes sense to say, for example, u ∈ e and e ∩ e ′ = ∅ , for an edge e ′ . For two vertices x, y ∈ V , let dist G ( x, y ) denote the distance between x and y in G , i.e., the length of a shortest path between x and y in G . The distance between a vertex z and an edge xy is the length of a shortest path between z and x, y , i.e., dist G ( z, xy ) = min { dist G ( z, v ) : v ∈ { x, y }} . The distance between two edges e, e ′ ∈ E is the length of a shortest path between e and e ′ , i.e., dist G ( e, e ′ ) = min { dist G ( u, v ) : u ∈ e, v ∈ e ′ } . In particular, this means that dist G ( e, e ′ ) = 0 if and only if e ∩ e ′ = . ∅

Clearly, G has a d.i.m. if and only if every connected component of G has a d.i.m.; from now on, we consider that G is connected, and connected components of induced subgraphs of G are mentioned as components .

Note that if G = ( V, E ) has a d.i.m. M , and V ( M ) denotes the vertex set of M then V \ V ( M ) is an independent set, say I , i.e.,

$$V \, \text{ has the partition } V = V ( M ) \cup I.$$

From now on, all vertices in I are colored white and all vertices in V ( M ) are colored black. According to [11], we also use the following notions: A partial black-white coloring of V is feasible if the set of white vertices is an independent set in G and every black vertex has at most one black neighbor. A complete black-white coloring of V is feasible if the set of white vertices is an independent set in G and every black vertex has exactly one black neighbor. Clearly, M is a d.i.m. of G if and only if the black vertices V ( M ) and the white vertices V \ V ( M ) form a complete feasible coloring of V .

## 2.2 Reduction steps, forbidden subgraphs, forced edges, and excluded edges

Various papers on this topic introduced and applied some forcing rules for reducing the graph G to a subgraph G ′ such that G has a d.i.m. if and only if G ′ has a d.i.m., based on the condition that for a d.i.m. M V , has the partition V = V ( M ) ∪ I such that all vertices in V ( M ) are black and all vertices in I are white (recall (1)).

A vertex v ∈ V is forced to be black if for every d.i.m. M of G v , ∈ V ( M ). Analogously, a vertex v ∈ V is forced to be white if for every d.i.m. M of G v / V , ∈ ( M ).

Clearly, if uv ∈ E and if u, v are forced to be black, then uv is contained in every (possible) d.i.m. of G .

An edge e ∈ E is a forced edge of G if for every d.i.m. M of G e , ∈ M . Analogously, an edge e ∈ E is an excluded edge of G if for every d.i.m. M of G e , ∈ M .

/negationslash

For the correctness of the reduction steps, we have to argue that G has a d.i.m. if and only if the reduced graph G ′ has one (provided that no contradiction arises in the vertex coloring, i.e., it is feasible).

Then let us introduce two reduction steps which will be applied later.

Vertex Reduction. Let u ∈ V ( G ). If u is forced to be white, then

- ( ) i color black all neighbors of u , and
- ( ii ) remove u from G .

Let G ′ be the reduced subgraph. Clearly, Vertex Reduction is correct, i.e., G has a d.i.m. if and only if G ′ has a d.i.m.

## Edge Reduction. Let uv ∈ E G ( ). If u and v are forced to be black, then

- ( ) i color white all neighbors of u and of v (other than u and v ), and
- ( ii ) remove u and v (and the edges containing u or v ) from G .

Again, clearly, Edge Reduction is correct, i.e., G has a d.i.m. if and only if the reduced subgraph G ′ has a d.i.m.

The subsequent notions and observations lead to some possible reductions (some of them are mentioned e.g. in [3, 4, 5]).

Observation 1 ([3, 4, 5]) . Let M be a d.i.m. of G .

- ( ) i M contains at least one edge of every odd cycle C 2 k +1 in G k , ≥ 1 , and exactly one edge of every odd cycle C 3 , C 5 , C 7 in G .
- ( ii ) No edge of any C 4 can be in M .
- ( iii ) For each C 6 either exactly two or none of its edges are in M .

## Proof. See e.g. Observation 2 in [4].

In what follows, we will also refer to Observation 1 ( ) (with respect to i C 3 ) as to the triangle-property , and to Observation 1 ( ii ) as to the C 4 -property .

Since by Observation 1 ( ), every triangle contains exactly one i M -edge, and the pairwise distance of M -edges is at least 2, we have:

## Corollary 1. If G has a d.i.m. then G is K 4 -free.

Assumption 1. From now on, by Corollary 1, we assume that the input graph is K 4 -free (else it has no d.i.m.).

Clearly, it can be checked (directly) in polynomial time whether the input graph is K 4 -free.

By Observation 1 ( ) with respect to i C 3 and the distance property, we have the following:

Observation 2. The mid-edge of any diamond in G and the two peripheral edges of any induced butterfly are forced edges of G .

Assumption 2. From now on, by Observation 2, we assume that the input graph is (diamond,butterfly)-free.

In particular, we can apply the Edge Reduction to each mid-edge of any induced diamond and to each peripheral edge of any induced butterfly; that can be done in polynomial time.

Here is an example for excluded edges: By Observation 1 ( ), there is exactly one i M -edge in the C 3 ( v , v 1 2 , v 3 ). Since G is K 4 -and diamond-free, every vertex v / ∈ { v , v 1 2 , v 3 } which contacts the C 3 ( v , v 1 2 , v 3 ) has exactly one neighbor in ( v , v 1 2 , v 3 ).

A paw has four vertices, say v , v 1 2 , v 3 , v 4 such that v , v 1 2 , v 3 induce a C 3 and v 4 contacts exactly one vertex in v , v 1 2 , v 3 , say v v 3 4 ∈ E . Thus, the edge v v 3 4 ∈ E is excluded.

## 2.3 The distance levels of an M -edge xy in a P 3

Based on [5], we first describe some general structure properties for the distance levels of an edge in a d.i.m. M of G . Since G is ( K 4 ,diamond,butterfly)-free, we have:

Observation 3. For every vertex v of G N v , ( ) is the disjoint union of isolated vertices and at most one edge. Moreover, for every edge uv ∈ E , there is at most one common neighbor of u and v .

Since it is trivial to check whether G has a d.i.m. M with exactly one edge, from now on we can assume that | M | ≥ 2.

Recall that the distance dist G ( a, b ) between two vertices a, b in graph G is the number of edges in a shortest path in G between a and b .

Theorem 2 ([1]) . Every connected P t -free graph G = ( V, E ) admits a vertex v ∈ V such that dist G ( v, w ) ≤ ⌊ t/ 2 ⌋ for every w ∈ V .

We call such a vertex v a central vertex; more exactly, a central vertex in G has shortest distance to every other vertex in G . Theorem 2 implies that every connected P 9 -free graph G admits a central vertex v ∈ V such that dist G ( v, w ) ≤ 4 for every w ∈ V . For a central vertex v and a neighbor u of v , i.e., uv ∈ E , let

$$N _ { i } ( u v ) \coloneqq \{ z \in V \, \colon d i s t _ { G } ( z, u v ) = i \}$$

denote the distance levels of uv , i ≥ 1. Then by Theorem 2, for every edge uv ∈ E , we have

$$N _ { k } ( u v ) = \emptyset \text{ for every } k \geq 5.$$

Observation 4. For every central vertex v in G , every edge uv ∈ E is part of a P 3 of G .

Proof. Let v be a central vertex in G , and suppose to the contrary that not every edge uv ∈ E is part of a P 3 of G , say ( u, v, w ) induce a C 3 in G such that uv is not part of a P 3 , i.e., N u [ ] = N v [ ] = { u, v, w } . Clearly, in this case, w has more neighbors than v in G since G itself is no C 3 , i.e., w has a neighbor x with xu / E ∈ and xv / E ∈ (else there is a diamond or K 4 ). Moreover, w is not part of a triangle with x and y (else there is a butterfly in G ). Then for every vertex y / ∈ { u, v, w } , dist G ( w,y ) &lt; dist G ( v, y ), which is a contradiction.

$$\text{Thus, Observation 4 is shown.}$$

Now assume that v is a central vertex in G such that every edge uv ∈ E is part of a P 3 of G . Then one could check for any edge uv ∈ E (with central vertex v ), whether there is a d.i.m. M of G with uv ∈ M , and one could conclude: Either G has a d.i.m. M with v ∈ V ( M ), or G has no d.i.m. M with v ∈ V ( M ); in particular, in the latter case, if none of the edges uv is in a d.i.m. then v is white and one can apply the Vertex Reduction to v and in particular remove v .

Now assume that x is a central vertex (as in Observation 4), and let xy ∈ M be an M -edge for which there is a vertex r such that { r, x, y } induce a P 3 with edge rx ∈ E . By the assumption that xy ∈ M , we have that x and y are black, and it could lead to a feasible xy -coloring (if no contradiction arises).

$$\text{Let } N _ { 0 } ( x y ) \coloneqq \{ x, y \} \text{ and for } i \geq 1, \text{ let }$$

$$N _ { i } ( x y ) \coloneqq \{ z \in V \, \colon d i s t _ { G } ( z, x y ) = i \}$$

denote the distance levels of xy . Recall (2) which also shows that N 5 ( xy ) = ∅ . We consider a partition of V into N i = N xy i ( ), 0 ≤ i ≤ 4, with respect to the edge xy (under the assumption that xy ∈ M ).

Observation 5. If v ∈ N i for i ≥ 4 then v is an endpoint of an induced P 6 , say with vertices v, v 1 , v 2 , v 3 , v 4 , v 5 such that v , v 1 2 , v 3 , v 4 , v 5 ∈ { x, y } ∪ N 1 ∪ . . . ∪ N i -1 and with edges vv 1 ∈ E v v , 1 2 ∈ E v v , 2 3 ∈ E v v , 3 4 ∈ E v v , 4 5 ∈ E . Analogously, if v ∈ N 3 then v is an endpoint of a corresponding induced P 5 .

Proof. If i ≥ 5 then clearly there is such a P 6 . Thus, assume that v ∈ N 4 . Then v 1 ∈ N 3 and v 2 ∈ N 2 . Recall that y, x, r induce a P 3 . If v r 2 ∈ E then v, v 1 , v 2 , r, x, y induce a

P 6 . Thus assume that v r 2 / E ∈ . Let v 3 ∈ N 1 be a neighbor of v 2 . Now, if v x 3 ∈ E then v, v 1 , v 2 , v 3 , x, r induce a P 6 , and if v x / E 3 ∈ but v y 3 ∈ E then v, v 1 , v 2 , v 3 , y, x induce a P 6 . Analogously, if v ∈ N 3 then v is an endpoint of an induced P 5 (which could be part of the P 6 above). Thus, Observation 5 is shown.

Recall that by (1), V = V ( M ) ∪ I is a partition of V where V ( M ) is the set of black vertices and I is the set of white vertices which is independent.

Since we assume that xy ∈ M (and is an edge in a P 3 ), clearly, N 1 ⊆ I and thus:

N 1

$$N _ { 1 } \text{ is an independent set of white vertices.}$$

Moreover, no edge between N 1 and N 2 is in M . Since N 1 ⊆ I and all neighbors of vertices in I are in V ( M ), we have:

$$G [ N _ { 2 } ] & \text{is the disjoint union of edges and isolated vertices.}$$

Let M 2 denote the set of edges uv ∈ E with u, v ∈ N 2 and let S 2 = { u , . . . , u 1 k } denote the set of isolated vertices in N 2 ; N 2 = V ( M 2 ) ∪ S 2 is a partition of N 2 . Obviously:

$$M _ { 2 } \subseteq M \text{ and } S _ { 2 } \subseteq V ( M ).$$

If for xy ∈ E , an edge e ∈ E is contained in every d.i.m. M of G with xy ∈ M , we say that e is an xy -forced M -edge, and analogously, if an edge e ∈ E is contained in no d.i.m. M of G with xy ∈ M , we say that e is xy -excluded . The Edge Reduction for forced edges can also be applied for xy -forced edges (then, in the unsuccessful case, G has no d.i.m. containing xy ), and correspondingly for xy -forced white vertices (resulting from the black color of x and y ), the Vertex Reduction can be applied.

Obviously, by (5), we have:

$$& \text{Every edge in } M _ { 2 } \text{ is an } x y \text{-forced } M \text{-edge}.$$

Thus, from now on, after applying the Edge Reduction for M 2 -edges, we can assume that V ( M 2 ) = ∅ , i.e., N 2 = S 2 = { u , . . . , u 1 k } . For every i ∈ { 1 , . . . , k } , let u ′ i ∈ N 3 denote the M -mate of u i (i.e., u u i ′ i ∈ M ). Let M 3 = { u u i ′ i : 1 ≤ i ≤ k } denote the set of M -edges with one endpoint in S 2 (and the other endpoint in N 3 ). Obviously, by (5) and the distance condition for a d.i.m. M , the following holds:

No edge with both ends in N 3 and no edge between N 3 and N 4 is in M. (7)

As a consequence of (7) and the fact that every triangle contains exactly one M -edge (recall Observation 1 ( )), we have: i

For every C 3 abc with a ∈ N , 3 and b, c ∈ N , bc 4 ∈ M is an xy -forced M -edge . (8)

This means that for the edge bc , the Edge Reduction can be applied, and from now on, we can assume that there is no such triangle abc with a ∈ N 3 and b, c ∈ N 4 , i.e., for every edge uv ∈ E in N 4 :

$$N ( u ) \cap N ( v ) \cap N _ { 3 } = \emptyset.$$

According to (5) and the assumption that V ( M 2 ) = ∅ (recall N 2 = { u , . . . , u 1 k } ), let:

$$T _ { o n e } \coloneqq \{ t \in N _ { 3 } \, \colon | N ( t ) \cap N _ { 2 } | = 1 \},$$

$$T _ { i } \coloneqq T _ { o n e } \cap N ( u _ { i } ), \, 1 \leq i \leq k, \, \text{and}$$

S 3 := N 3 \ T one .

By definition, T i is the set of private neighbors of u i ∈ N 2 in N 3 (note that u ′ i ∈ T i ), T 1 ∪ . . . ∪ T k is a partition of T one , and T one ∪ S 3 is a partition of N 3 .

Lemma 1 ([5]) . The following statements hold:

- ( ) i For all i ∈ { 1 , . . . , k } , T i ∩ V ( M ) = { u ′ i } .
- ( ii ) For all i ∈ { 1 , . . . , k } , T i is the disjoint union of vertices and at most one edge.
- ( iii ) G N [ 3 ] is bipartite.
- ( iv ) S 3 ⊆ I , i.e., S 3 is an independent subset of white vertices.

/negationslash

- ( v ) If a vertex t i ∈ T i sees two vertices in T j , i = j , i, j ∈ { 1 , . . . , k } , then u t i i ∈ M is an xy -forced M -edge.

Proof. ( ): i Holds by definition of T i and by the distance condition of a d.i.m. M .

- ( ii ): Holds by Observation 3.
- ( iii ): Follows by Observation 1 ( ) since every odd cycle in i G must contain at least one M -edge, and by (7).
- ( iv ): If v ∈ S 3 := N 3 \ T one , i.e., v sees at least two M -vertices then clearly, v ∈ I , and thus, S 3 ⊆ I is an independent subset (recall that I is an independent set).
- ( v ): Suppose that t 1 ∈ T 1 sees a and b in T 2 . If ab ∈ E then u , a, b, t 2 1 would induce a diamond in G . Thus, ab / E ∈ and now, u , a, b, t 2 1 induce a C 4 in G ; by Observation 1 ( ii ), no edge in the C 4 is in M , and by (7), the only possible M -edge for dominating t 1 a, t 1 b is u t 1 1 , i.e., t 1 = u ′ 1 .

By Lemma 1 ( iv ) and the Vertex Reduction for the white vertices of S 3 , we can assume:

- (A1) S 3 = , i.e., ∅ N 3 = T 1 ∪ . . . ∪ T k .

By Lemma 1 ( ), we can assume: v

/negationslash

- (A2) For i, j ∈ { 1 , . . . , k } , i = , every vertex j t i ∈ T i has at most one neighbor in T j .

In particular, if for some i ∈ { 1 , . . . , k } , T i = ∅ , then there is no d.i.m. M of G with xy ∈ M , and if | T i | = 1, say T i = { t i } , then u t i i is an xy -forced M -edge. Thus, we can assume:

## (A3) For every i ∈ { 1 , . . . , k } , | T i | ≥ 2.

/negationslash

Let us say that a vertex t ∈ T i , 1 ≤ i ≤ k , is an out-vertex of T i if it is adjacent to some vertex of T j with j = , or it is adjacent to some vertex of i N 4 , and t is an in-vertex of T i otherwise.

For finding a d.i.m. M with xy ∈ M , one can remove all but one in-vertices; that can be done in polynomial time. In particular, if there is an edge between two in-vertices t 1 t 2 ∈ E t , t , 1 2 ∈ T i , then either t 1 or t 2 is black, and thus, T i is completely colored. Thus, let us assume:

- (A4) For every i ∈ { 1 , . . . , k } , T i has at most one in-vertex.

Lemma 2. Assume that G has a d.i.m. M with xy ∈ M . Then:

/negationslash

- ( ) i For every i = j , there are at most two edges between T i and T j .

/negationslash

- ( ii ) If there are two edges between T i and T j , say t t i j ∈ E and t t ′ i ′ j ∈ E for t , t i ′ i ∈ T i and t j , t ′ j ∈ T j , t i = t ′ i , t j = t ′ j , then every vertex in ( T i ∪ T j ) \ { t , t i j , t ′ i , t ′ j } is white.

/negationslash

Proof. ( ): i Suppose to the contrary that there are three edges between T 1 and T 2 , say t 1 t 2 ∈ E t t , ′ 1 ′ 2 ∈ E , and t ′′ 1 t ′′ 2 ∈ E for t , t i ′ i , t ′′ i ∈ T i , i = 1 2. , By (A2), t , t i ′ i , t ′′ i are distinct. Then t 1 is black if and only if t 2 is white, t ′ 1 is black if and only if t ′ 2 is white, and t ′′ 1 is black if and only if t ′′ 2 is white. Without loss of generality, assume that t 1 is black, and t 2 is white. Then t ′ 1 is white, and t ′ 2 is black, but now, t ′′ 1 and t ′′ 2 are white, which is a contradiction.

/negationslash

/negationslash

- ( ii ): Let t 1 t 2 ∈ E t t , ′ 1 ′ 2 ∈ E , be two such edges between T 1 and T 2 . By (A2), t 1 = t ′ 1 , and t 2 = t ′ 2 . Then again, t 1 or t ′ 1 is black as well as t 2 or t ′ 2 is black, and thus, every other vertex in T 1 or T 2 is white.

Thus Lemma 2 is shown.

By Lemma 2 ( ), we can assume: i

/negationslash

- (A5) For i, j ∈ { 1 , . . . , k } , i = , there are at most two edges between j T i and T j .

Recall that | T i | ≥ 2. If there is an edge in T i , say ab ∈ E with a, b ∈ T i and there is a third vertex c ∈ T i then either a or b is black, and thus, by Lemma 1 ( ), i c is forced to be white, and by the Vertex Reduction and by Lemma 2 ( ii ), we can assume:

- (A6) If there is an edge in T i then | T i | = 2. Analogously, if there are two edges between T i and T j then | T i | = 2 and | T j | = 2.

Then let us introduce the following forcing rules (which are correct). Since no edge in N 3 is in M (recall (7)), we have:

- (R1) All N 3 -neighbors of a black vertex in N 3 must be colored white, and all N 3 -neighbors of a white vertex in N 3 must be colored black.

Moreover, we have:

- (R2) Every T i , i ∈ { 1 , . . . , k } , should contain exactly one vertex which is black. Thus, if t ∈ T i is black then all the remaining vertices in T i \ { } t must be colored white.
- (R3) If all but one vertices of T i , 1 ≤ i ≤ k , are white and the final vertex t ∈ T i is not yet colored, then t must be colored black.

Since no edge between N 3 and N 4 is in M (recall (7)), we have:

- (R4) For every edge st ∈ E with t ∈ N 3 and s ∈ N 4 , s is white if and only if t is black and vice versa.

Subsequently, for checking if G has a d.i.m. M with xy ∈ M , we consider the cases N 4 = ∅ and N 4 = . ∅

/negationslash

Then let us introduce the following recursive algorithm which formalizes the approach we will adopt to check if G has a d.i.m.

## Algorithm DIM( G )

Input. A connected P 9 - and ( K 4 ,diamond,butterfly)-free graph G = ( V, E Output. A d.i.m. of G or the proof that G has no d.i.m.

).

- (A) Compute a central vertex, say x , of G such that dist G ( x, u ) ≤ 4 for every u ∈ V and every edge xy ∈ E is part of a P 3 of G .
- (B) For each edge xy ∈ E of G [contained in a P 3 of G ] do:
- (B.1) compute the distance levels N i with respect to xy and apply the reduction steps as shown above: if no contradiction arose and if assumptions (A1)-(A6) hold, then go to Step (B.2), else take another edge with x ;
- (B.2) check if G has a d.i.m. M with xy ∈ M ; if yes , then return it, and STOP.
- (C) Apply the Vertex Reduction to x [and in particular remove x ]; let G ′ denote the resulting graph, where the neighbors of x in G are colored by black; if G ′ is disconnected, then execute Algorithm DIM( H ) for each connected component H of G ′ ; otherwise, go to Step (B), with G := G ′ .
- (D) Return ' G has no d.i.m.' and STOP.

Then, by the above, Algorithm DIM( G ) is correct and can be executed in polynomial time as soon as Step (B.2) can be so.

Then in what follows let us try to show that Step (B.2) can be solved in polynomial time, with the agreement that G is ( K 4 ,diamond,butterfly)-free and enjoys assumptions (A1)-(A6): in particular recall (2) that N k = ∅ for k ≥ 5.

/negationslash

Thus we consider the cases N 4 = ∅ and N 4 = . Let ∅ A xy := { x, y }∪ N 1 ∪ N 2 ∪ N 3 , and recall N 4 = V \ A xy .

## 3 The Case N 4 = ∅

In this section, we show that for the case N 4 = ∅ , one can check in polynomial time whether G has a d.i.m. M with xy ∈ M ; we consider the feasible xy -colorings for G A [ xy ]. Recall that for every edge uv ∈ M u , and v are black, for I = V ( G ) \ V ( M ), every vertex in I is white, N 2 = S 2 = { u , . . . , u 1 k } and all u i , 1 ≤ i ≤ k , are black, T i = N u ( i ) ∩ N 3 , and recall assumptions (A1)-(A6) and rules (R1)-(R4). In particular, by (A1), S 3 = ∅ , i.e., N 3 = T 1 ∪ . . . ∪ T k .

Clearly, in the case N 4 = ∅ , all the components of G S [ 2 ∪ N 3 ] can be independently colored. Every component with at most three S 2 -vertices has a polynomial number of feasible xy -colorings. Thus, we can focus on components K with at least four S 2 -vertices.

A P 2 ( u, v ) in G N [ 3 ] is isolated in G N [ 3 ] if it is not part of a P 3 in G N [ 3 ].

Claim 1. If every P 2 in component K in G S [ 2 ∪ N 3 ] is isolated then K has at most three S 2 -vertices.

Proof. Suppose to the contrary that K has at least four S 2 -vertices, say u , u 1 2 , u 3 , u 4 , and without loss of generality, assume that T 2 contacts T 1 and T 3 , say t ′ 1 t 2 ∈ E and t ′ 2 t 3 ∈ E for t ′ 1 ∈ T 1 , t 2 , t ′ 2 ∈ T 2 , and t 3 ∈ T 3 . By the isolated edges, ( u , t 1 ′ 1 , t 2 , u 2 , t ′ 2 , t 3 , u 3 ) induce a P 7 .

## Case 1. T 4 contacts T 1 or T 3 .

Without loss of generality, assume that T 4 contacts T 3 , i.e., there is a t 4 ∈ T 4 which contacts a vertex in T 3 . Clearly, t 3 t 4 / E ∈ since t ′ 2 t 3 ∈ E is isolated. Then t ′ 3 t 4 / E ∈ for a second vertex t ′ 3 ∈ T 3 , and clearly, t ′ 3 and t 4 do not contact the edges t ′ 1 t 2 and t ′ 2 t 3 but then ( u , t 1 ′ 1 , t 2 , u 2 , t ′ 2 , t 3 , u 3 , t ′ 3 , t 4 ) induce a P 9 , which is a contradiction.

## Case 2. T 4 contacts T 2 but does not contact T 1 and T 3 .

Let t 4 ∈ T 4 contact T 2 . Clearly, by the isolated edges, t 4 does not contact t 2 , t ′ 2 ∈ T 2 . Thus assume that t ′′ 2 t 4 ∈ E for a third vertex t ′′ 2 ∈ T 2 . By (A3), there is a second vertex t ′ 4 ∈ T 4 and a second vertex t ′ 3 ∈ T 3 , and clearly, t 3 t ′ 3 / E ∈ , t 4 t ′ 4 / E ∈ and t ′ 4 does not contact T 3 and t ′ 4 does not contact t ′ 2 , t ′′ 2 ∈ T 2 . But then ( t ′ 4 , u 4 , t 4 , t ′′ 2 , u 2 , t ′ 2 , t 3 , u 3 , t ′ 3 ) induce a P 9 , which is a contradiction.

Thus, Claim 1 is shown.

From now on, we can assume that there is at least one P 3 with contact between T i and T i +1 in K .

Claim 2. For any P 3 's ( a, b, c ) and ( d, e, f ) in G N [ 3 ] such that d, e, f are not in the T i 's of a, b, c , there is an edge between { a, b, c } and { d, e, f } .

Proof. Suppose to the contrary that there is no such edge between the P 3 's ( a, b, c ) and ( d, e, f ) in G N [ 3 ]. From Lemma 1 ( ii ), a, b, c are in at least two T i 's; assume that a ∈ T 1 . Then, by Lemma 1 ( v ) and since ab ∈ E bc , ∈ E , we have c / T ∈ 1 ; let c ∈ T 2 , i.e., u c / E 1 ∈ . Then either b / T ∈ 1 or b / T ∈ 2 ; without loss of generality, let b / T ∈ 1 . Analogously, since d, e, f are not in T 1 ∪ T 2 , assume that d ∈ T 3 and e, f / T ∈ 3 .

Let P be any induced path in G between u 1 and u 3 through N 1 ∪ { x, y } . Then the subgraph of G induced by ( c, b, a, u 1 ), P , and ( u , d, e, f 3 ) contains an induced P 9 , which is a contradiction. Thus, Claim 2 is shown.

For a P 5 P = ( a, b, c, d, e ) in G N [ 3 ] with a ∈ T i and b, c, d, e / T ∈ i , vertex a is a special P 5 -endpoint of P in G N [ 3 ].

Claim 3. There is no P 5 ( a, b, c, d, e ) in G N [ 3 ] with special P 5 -endpoint a .

Proof. Suppose to the contrary that ( a, b, c, d, e ) is a P 5 in G N [ 3 ] with special P 5 -endpoint a ∈ T i and b, c, d, e / T ∈ i . But then by Observation 5, vertex a is the midpoint of a P 9 , which is a contradiction. Thus, Claim 3 is shown.

Claim 4. If C = ( t , u , t , t i i ′ i j , t h , t /lscript ) is a C 6 in G S [ 2 ∪ N 3 ] with exactly one vertex u i ∈ S 2 and t , t i ′ i ∈ T i , t j ∈ T j , t h ∈ T h , t /lscript ∈ T /lscript (possibly j = h or h = /lscript ) then t j and t /lscript are xy -forced to be black, i.e., u t j j and u t /lscript /lscript are xy -forced M -edges, and thus, T j and T /lscript are completely colored.

Proof. By (7), no edge in N 3 is in M . By Observation 1 ( iii ), either exactly two or none of the edges in C are in M . Since C has exactly one vertex u i ∈ S 2 , u t i i and u t i ′ i are the only edges of C which are not in N 3 , and clearly, either u t i i / M ∈ or u t i ′ i / M ∈ . Thus, by Observation 1 ( iii ), no edge in C is in M , i.e., t i and t ′ i are white, and t j as well as t /lscript are xy -forced to be black. Thus, Claim 4 is shown.

After the Edge Reduction step, we can assume that there is no such C 6 in G S [ 2 ∪ N 3 ], i.e., every C 6 in G S [ 2 ∪ N 3 ] has either two vertices of S 2 or none of it.

Claim 5. If C is a C 7 in G S [ 2 ∪ N 3 ] then C has exactly two vertices in S 2 , say C = ( t , u , t , t i i ′ i j , u j , t ′ j , t h ) , and then t h is xy -forced to be black, i.e., u t h h is an xy -forced M -edge.

Proof. Let C be a C 7 in G S [ 2 ∪ N 3 ]. Recall that by Lemma 1 ( iii ), there is no C 7 in G N [ 3 ]. Thus, | V ( C ) ∩ S 2 | ≥ 1, and clearly, by (A1), no vertex in V ( C ) ∩ N 3 contacts two vertices in V ( C ) ∩ S 2 , i.e., | V ( C ) ∩ S 2 | ≤ 2.

If there is exactly one S 2 -vertex in a C 7 in G N [ 3 ], say C = ( t 1 , u 1 , t ′ 1 , t 2 , t , t ′ ′′ , t ′′′ ) with t 1 , t ′ 1 ∈ T 1 then t 2 , t , t ′ ′′ , t ′′′ / T ∈ 1 , but now, ( t ′ 1 , t 2 , t , t ′ ′′ , t ′′′ ) induce a P 5 with special P 5 -endpoint t ′ 1 ∈ T 1 such that t 2 , t , t ′ ′′ , t ′′′ / T ∈ 1 , which is a contradiction to Claim 3.

Now assume that C = ( t 1 , u 1 , t ′ 1 , t 2 , u 2 , t ′ 2 , t 3 ) is a C 7 in G S [ 2 ∪ N 3 ]. Suppose to the contrary that t 3 is white. Then t 1 and t ′ 2 are black which implies that t ′ 1 and t 2 are white, which is a contradiction since t ′ 1 t 2 ∈ E . Thus, t 3 is xy -forced to be black, i.e., u t 3 3 is an xy -forced M -edge, and Claim 5 is shown.

After the Edge Reduction step, we can assume that there is no C 7 in G S [ 2 ∪ N 3 ].

Claim 6. If there is a C 9 C in G S [ 2 ∪ N 3 ] then | V ( C ) ∩ S 2 | = 3 , say V ( C ) ∩ S 2 = { u , u 1 2 , u 3 } , and for the component K in G S [ 2 ∪ N 3 ] containing C , we have K = G u ,u ,u [ { 1 2 3 } ∪ T 1 ∪ T 2 ∪ T 3 ] .

Proof. Let C be a C 9 in G S [ 2 ∪ N 3 ]. Recall that by Lemma 1 ( iii ), there is no C 9 in G N [ 3 ], i.e., | V ( C ) ∩ S 2 | ≥ 1, and clearly, | V ( C ) ∩ S 2 | ≤ 3.

If C contains only one S 2 -vertex then, as in the proof of Claim 5, it leads to a P 5 in N 3 with corresponding special P 5 -endpoint, which is a contradiction to Claim 3. Thus, | V ( C ) ∩ S 2 | ≥ 2.

First assume that | V ( C ) ∩ S 2 | = 2. If C = ( t 1 , u 1 , t ′ 1 , t 2 , u 2 , t ′ 2 , t 3 , t 4 , t 5 ) (possibly t 3 , t 4 ∈ T 3 or t 4 , t 5 ∈ T 4 ) then this leads to a P 5 ( t ′ 2 , t 3 , t 4 , t 5 , t 1 ) with special P 5 -endpoint t 1 , which is a contradiction to Claim 3. If C = ( t 1 , u 1 , t ′ 1 , t 2 , t 3 , u 3 , t ′ 3 , t 4 , t 5 ) then t 2 is xy -forced to be black: Suppose to the contrary that t 2 is white. Then t ′ 1 and t 3 are black, which implies that t 1 and t ′ 3 are white, but now, t 4 and t 5 are black, which is a contradiction since there is no M -edge in N 3 . Thus, u t 2 2 is an xy -forced M -edge, and after the Edge Reduction, | V ( C ) ∩ S 2 | = 2 is impossible.

Thus, | V ( C ) ∩ N 2 | = 3; let C = ( t 1 , u 1 , t ′ 1 , t 2 , u 2 , t ′ 2 , t 3 , u 3 , t ′ 3 ) be a C 9 with three such S 2 -vertices u , u 1 2 , u 3 . Suppose to the contrary that there is a vertex t 4 ∈ T 4 which contacts C , say t ′ 3 t 4 ∈ E . Clearly, by Lemma 1 ( v ), t 4 t 3 / E ∈ . Since ( u , t 1 ′ 1 , t 2 , u 2 , t ′ 2 , t 3 , u 3 , t ′ 3 , t 4 ) do not induce a P 9 , we have t 4 t ′ 1 ∈ E or t 4 t 2 ∈ E or t 4 t ′ 2 ∈ E .

If t 4 t ′ 1 ∈ E then ( t 2 , t ′ 1 , t 4 , t ′ 3 , t 1 ) would induce a P 5 in N 3 with special P 5 -endpoint t 2 , which is impossible by Claim 3. Similarly, if t 4 t ′ 2 ∈ E then ( t 3 , t ′ 2 , t 4 , t ′ 3 , t 1 ) would induce a P 5 in N 3 with special P 5 -endpoint t 1 , which is a contradiction to Claim 3.

Thus, t 4 t 2 ∈ E which leads to a C 7 ( t 2 , u 2 , t ′ 2 , t 3 , u 3 , t ′ 3 , t 4 ). But then, by Claim 5, t 4 is xy -forced to be black, i.e., u t 4 4 is an xy -forced M -edge, and after the Edge Reduction, there is no such C 7 . Thus, Claim 6 is shown.

Corollary 2. Every component in G S [ 2 ∪ N 3 ] with at least four S 2 -vertices is C 9 -free.

Lemma 3. In the case N 4 = ∅ , for every component K in G S [ 2 ∪ N 3 ] , a complete coloring of K (if there is no contradiction) can be done in polynomial time.

Proof. For finding a complete feasible xy -coloring of component K (or a contradiction), we first use Vertex Reduction and Edge Reduction as in the previous results.

Let V ( K ) ∩ N 3 = T 1 ∪ . . . ∪ T h (recall that h ≥ 4 since otherwise, a complete feasible xy -coloring of K can be done in polynomial time). Clearly, for every i , 1 ≤ i ≤ h , we have | T i | ≥ 2.

If every T i in K would have only one out-vertex t i ∈ T i , then the procedure starts by fixing a coloring of T 1 ; for every i , 1 ≤ i ≤ h , there are only two possible colorings of T i since by (A4), every T i has at most one in-vertex. If the already colored out-vertex t i ∈ T i with contact to t i +1 ∈ T i +1 is white then t i +1 is black, the in-vertex of T i +1 is white, and T i +1 is completely colored. Analogously, if t i is black then t i +1 is white, the in-vertex of T i +1 is black, and T i +1 is completely colored.

/negationslash

Thus, we can assume that there is a T i with at least two out-vertices (such that at least one of them is white). In this case, the procedure starts by fixing a coloring of T 1 with at least two out-vertices (this can be repeated for all | T 1 | colorings of T 1 ) and applies the forcing rules, and then the next step of the procedure is using a white out-vertex t 1 ∈ T 1 , say with contact to T 2 , such that the neighbor t 2 ∈ T 2 of t 1 is black. If t 2 contacts only T 1 then t 2 does not play any role for the procedure. If t 2 contacts some T j , j = 1 2, the , problem is how T j can be completely colored.

Now we can assume that every black out-vertex (which was already colored by a white neighbor in the previous step) contacts at least two T i 's, say, t 2 ∈ T 2 was colored black by a white vertex t ′ 1 ∈ T 1 with t ′ 1 t 2 ∈ E (i.e., T 1 was already colored), and t 2 t 3 ∈ E for t 3 ∈ T 3 but T 3 is not yet completely colored. Then t 3 is white, and if t 3 t ′ 3 ∈ E for another t ′ 3 ∈ T 3 then t ′ 3 is black and T 3 is completely colored. Thus assume that t 3 t ′ 3 / E ∈ for any t ′ 3 ∈ T 3 . If t 3 is the only out-vertex in T 3 then the in-vertex is black (recall that by (A4), every T i has at most one in-vertex) and T 3 is completely colored. Thus assume that t ′ 3 is an out-vertex, say t ′ 3 t 4 ∈ E for t 4 ∈ T 4 . We first show:

Claim 7. If there is any contact between the P 3 ( t ′ 1 , t 2 , t 3 ) and the P 2 ( t ′ 3 , t 4 ) then T 3 is completely colored.

Proof. Clearly, t 3 t ′ 3 / E ∈ , t 3 t 4 / E ∈ , and t 2 t ′ 3 / E ∈ . If t ′ 1 t ′ 3 ∈ E then t ′ 3 is black and T 3 is completely colored. Thus assume that t ′ 1 t ′ 3 / E ∈ . If t 2 t 4 ∈ E then t 4 is white and thus, t ′ 3 is black and T 3 is completely colored. Thus assume that t 2 t 4 / E ∈ .

Finally, if t ′ 1 t 4 ∈ E then ( t ′ 1 , t 2 , t 3 , u 3 , t ′ 3 , t 4 ) induce a C 6 , which is impossible by Claim 4 and the Edge Reduction.

Thus, T 3 is completely colored.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00978v3-figure-ba6d1e51-c786-4823-868d-1892849526f7.jpg)

Now we assume:

$$( t _ { 1 } ^ { \prime }, t _ { 2 }, t _ { 3 } ) \mathbb { O } ( t _ { 3 } ^ { \prime }, t _ { 4 } ).$$

Moreover, ( u , t 1 ′ 1 , t 2 , t 3 , u 3 , t ′ 3 , t 4 , u 4 ) induce a P 8 in G . Clearly, | T 1 | ≥ 2 and | T 4 | ≥ 2; let t 1 ∈ T 1 be a second vertex in T 1 and t ′ 4 ∈ T 4 be a second vertex in T 4 .

## Claim 8. If t 4 t ′ 4 / E ∈ then T 3 is completely colored.

Proof. If t 4 t ′ 4 / E ∈ then clearly, t ′ 3 t ′ 4 / E ∈ . Since ( u , t 1 ′ 1 , t 2 , t 3 , u 3 , t ′ 3 , t 4 , u 4 , t ′ 4 ) do not induce a P 9 in G , we have t ′ 1 t ′ 4 ∈ E or t 2 t ′ 4 ∈ E or t 3 t ′ 4 ∈ E . If t 3 t ′ 4 ∈ E then | T 3 | = 2 (recall (A6)) and T 3 is completely colored. Thus assume that t 3 t ′ 4 / ∈ E . Now, if t 2 t ′ 4 ∈ E then ( t 2 , t 3 , u 3 , t ′ 3 , t 4 , u 4 , t ′ 4 ) induce a C 7 , which is impossible by Claim 5 and the Edge Reduction. Thus, t 2 t ′ 4 / E ∈ which implies that t ′ 1 t ′ 4 ∈ E . But now, since t ′ 1 is white, t ′ 4 is black, t 4 is white, t ′ 3 is black, and T 3 is completely colored.

From now on, we assume:

t 4 t ′ 4 ∈ E.

## Case 1. t 1 t ′ 1 ∈ E .

Then t 1 is black. By Claim 2, ( t 2 , t ′ 1 , t 1 ) and ( t ′ 3 , t 4 , t ′ 4 ) do not induce a 2 P 3 . Recall that ( t 2 , t ′ 1 ) and ( t ′ 3 , t 4 ) induce a 2 P 2 . Thus, t 1 should contact ( t ′ 3 , t 4 , t ′ 4 ) or t ′ 4 should contact ( t 2 , t ′ 1 , t 1 ).

If t ′ 1 t ′ 4 ∈ E then t ′ 4 is black, t 4 is white, t ′ 3 is black, and T 3 is completely colored. Thus assume t ′ 1 t ′ 4 / E ∈ . Analogously, if t 1 t 4 ∈ E then t 4 is white, and t ′ 3 is black, and T 3 is completely colored. Thus assume t 1 t 4 / E ∈ .

If t 1 t 3 ∈ E then clearly, t 1 t ′ 3 / E ∈ , and if t 1 t 3 / E ∈ but t 1 t ′ 3 ∈ E then ( t 1 , t ′ 1 , t 2 , t 3 , u 3 , t ′ 3 ) induce a C 6 which is impossible by Claim 4 and the Edge Reduction. Thus, assume that t 1 t ′ 3 / E ∈ .

If t 2 t ′ 4 ∈ E then ( t 2 , t 3 , u 3 , t ′ 3 , t 4 , t ′ 4 ) induce a C 6 which is impossible by Claim 4 and the Edge Reduction. Thus, assume that t 2 t ′ 4 / E ∈ .

Now, t 1 t ′ 4 ∈ E is the only possible edge between ( t 2 , t ′ 1 , t 1 ) and ( t ′ 3 , t 4 , t ′ 4 ) but now, ( t 2 , t ′ 1 , t 1 , t ′ 4 , t 4 ) induce a P 5 with special endpoint t 2 , which is impossible by Claim 3. Thus, in Case 1, T 3 is completely colored.

## Case 2. t 1 t ′ 1 / E ∈ .

Recall that t ′ 1 and t 3 are white and ( t ′ 1 , t 2 , t 3 ) 0 © ( t ′ 3 , t 4 ). Clearly, t 1 t 2 / E ∈ , and since ( t 1 , u 1 , t ′ 1 , t 2 , t 3 , u 3 , t ′ 3 , t 4 , u 4 ) do not induce a P 9 in G , we have t 1 t 3 ∈ E or t 1 t ′ 3 ∈ E or t 1 t 4 ∈ E .

If t 1 t ′ 3 ∈ E then clearly, t 1 t 3 / E ∈ . But then ( t 1 , u 1 , t ′ 1 , t 2 , t 3 , u 3 , t ′ 3 ) induce a C 7 , which is impossible by Claim 5 and the Edge Reduction. Thus, assume t 1 t ′ 3 / ∈ E and either t 1 t 3 ∈ E or t 1 t 4 ∈ E .

## Case 2.1 t 1 t 3 / E ∈ .

Then t 1 t 4 ∈ E . First assume that t 1 is white, which implies that t 4 is black, and there is a black vertex t ′′ 1 ∈ T 1 . Clearly, t ′′ 1 t 1 / E ∈ , t ′′ 1 t ′ 1 / E ∈ , t ′′ 1 t 2 / E ∈ , and since t 4 is black, we have t ′′ 1 t 4 / E ∈ . Since ( t ′′ 1 , u 1 , t ′ 1 , t 2 , t 3 , u 3 , t ′ 3 , t 4 , u 4 ) do not induce a P 9 in G , we have t ′′ 1 t 3 ∈ E or t ′′ 1 t ′ 3 ∈ E .

If t ′′ 1 t ′ 3 ∈ E then t ′′ 1 t 3 / ∈ E , but now ( t ′′ 1 , u 1 , t ′ 1 , t 2 , t 3 , u 3 , t ′ 3 ) induce a C 7 , which is impossible by Claim 5 and the Edge Reduction. Thus, assume t ′′ 1 t ′ 3 / E ∈ which implies t ′′ 1 t 3 ∈ E . But now ( t ′′ 1 , u 1 , t 1 , t 4 , t ′ 3 , u 3 , t 3 ) induce a C 7 , which is impossible by Claim 5 and the Edge Reduction.

Thus t 1 is black which implies that t 4 is white, t ′ 3 is black, T 3 is completely colored, and Case 2.1 is done.

## Case 2.2 t 1 t 3 ∈ E .

Since t 3 is white, t 1 is black. Clearly, since t 1 t 3 ∈ E , we have t 1 t ′ 3 / E ∈ . If t 1 t 4 ∈ E then t 4 is white and thus, t ′ 3 is black and T 3 is completely colored. Thus, assume that t 1 t 4 / E ∈ .

If | T 1 | ≥ 3 then let t ′′ 1 ∈ T 1 be a second white vertex in T 1 . Then t ′′ 1 t 3 / E ∈ , and Case 2.1 applies for t ′′ 1 ∈ T 1 . Thus we have

$$| T _ { 1 } | = 2.$$

Next assume that the black out-vertex t 1 has a second white neighbor, say t 0 ∈ T 0 with t 0 t 1 ∈ E . Since ( t 0 , t 1 , t 3 , t 2 , t ′ 1 ) do not induce a P 5 with special endpoint t 0 (recall Claim 3), we have t 0 t 2 ∈ E . Recall that t ′ 1 t ′ 4 / ∈ E (else T 3 is completely colored) and t 2 t ′ 4 / ∈ E (else ( t 2 , t 3 , u 3 , t ′ 3 , t 4 , t ′ 4 ) induce a C 6 which is impossible by Claim 4 and the Edge Reduction).

Since ( t ′ 1 , t 2 , t 0 ) and ( t ′ 3 , t 4 , t ′ 4 ) do not induce a 2 P 3 (recall Claim 2), we have t 0 t ′ 3 ∈ E or t 0 t 4 ∈ E or t 0 t ′ 4 ∈ E . If t 0 t ′ 3 ∈ E or t 0 t ′ 4 ∈ E then t ′ 3 is black and T 3 is completely colored. Thus assume that t 0 t 4 ∈ E . But now, ( t 0 , t 1 , t 3 , u 3 , t ′ 3 , t 4 ) induce a C 6 which is impossible by Claim 4 and the Edge Reduction. Thus, t 1 has only one white neighbor, namely t 3 .

Next we show:

## Claim 9. t ′ 4 is no out-vertex.

Proof. Suppose to the contrary that t ′ 4 t 5 ∈ E for some t 5 ∈ T 5 . Recall that t 4 does not contact t ′ 1 , t 2 , t 3 . Since t ′ 4 is white (else T 3 is completely colored), t ′ 4 does not contact t ′ 1 , t 3 , and recall that t ′ 4 t 2 / E ∈ (else ( t 2 , t 3 , u 3 , t ′ 3 , t 4 , t ′ 4 ) induce a C 6 , which is impossible by Claim 4 and the Edge Reduction).

Recall that ( t ′ 1 , t 2 , t 3 ) and ( t 4 , t ′ 4 , t 5 ) do not induce a 2 P 3 . Thus, since t 4 and t ′ 4 do not contact ( t ′ 1 , t 2 , t 3 ), only t 5 could contact ( t ′ 1 , t 2 , t 3 ). Since t 2 and t 5 are black, we have t 5 t 2 / E ∈ . If t 5 t 3 ∈ E then clearly, t 5 t ′ 3 / E ∈ but then ( t 3 , u 3 , t ′ 3 , t 4 , t ′ 4 , t 5 ) induce a C 6 , which is impossible by Claim 4 and the Edge Reduction. Thus, t 5 t 3 / E ∈ . Now, if t 5 t ′ 1 ∈ E then ( t 1 , t 3 , t 2 , t ′ 1 , t 5 ) induce a P 5 with special endpoint t 5 , which is a contradiction by Claim 3.

Thus t 5 t ′ 1 / E ∈ , t 5 t 2 / E ∈ , and t 5 t 3 / E ∈ . But then ( t ′ 1 , t 2 , t 3 ) and ( t 4 , t ′ 4 , t 5 ) induce a 2 P 3 , which is a contradiction by Claim 2. Thus, Claim 9 is shown.

This implies that t 4 is the only out-vertex in T 4 .

Next we show:

Claim 10. The black vertex t 2 contacts only one T i (namely T 3 ) which is not yet completely colored.

/negationslash

Proof. Suppose to the contrary that t 2 contacts a second T i (apart from T 3 ) which is not yet completely colored. Then T i = T 4 since by the above T 4 = { t 4 , t ′ 4 } and t 2 is nonadjacent to t 4 , t ′ 4 . Then say T i = T 5 , i.e., t 2 contacts T 5 with t 2 t 5 ∈ E . Note that t 5 does not contact T 3 (else T 3 is completely colored) and does not contact T 4 (else, by Claim 9, t 5 t 4 ∈ E and then vertices t 2 , t 3 , u 3 , t ′ 3 , t 4 , t 5 would induce a C 6 according to

Claim 4). Since T 5 is not yet completely colored, T 5 is not contacted by t ′ 1 and t 3 , and furthermore (similarly to the above with respect to T 3 ) there is an out-vertex of T 5 say t ′ 5 ∈ T 5 (nonadjacent to t 5 ). Note that t ′ 5 does not contact T 3 (else, say t ′ 5 t ′′ 3 ∈ E with t ′′ 3 ∈ T 3 , vertices t 2 , t 3 , u 3 , t ′′ 3 , t ′ 5 , u 5 , t 5 induce a C 7 in G S [ 2 ∪ N 3 ]) and does not contact T 4 (else, by Claim 9, t ′ 5 t 4 ∈ E and then vertices u , t 1 ′ 1 , t 2 , t 5 , u 5 , t ′ 5 , t 4 , t ′ 3 , u 3 induce a P 9 ). Then vertices t ′ 5 , u 5 , t 5 , t 2 , t 3 , u 3 , t ′ 3 , t 4 , t ′ 4 induce a P 9 , which is a contradiction.

Thus, Claim 10 is shown.

Finally we show:

Claim 11. There is only one black vertex which contacts a T i which is not yet completely colored.

/negationslash

Proof. Suppose to the contrary that there are two such black vertices, say t 2 which contacts T 3 and t 6 which contacts T 7 such that T , T 3 7 are not yet completely colored. By Claim 10, t 2 does not contact T 7 and t 6 does not contact T 3 . If t ′ 1 = t ′ 5 then clearly, the P 3 's ( t ′ 1 , t 2 , t 3 ) and ( t ′ 5 , t 6 , t 7 ) do not induce a 2 P 3 but t 2 t 7 / E ∈ and t 6 t 3 / E ∈ . Thus, t ′ 1 t 6 ∈ E or t ′ 5 t 2 ∈ E , say without loss of generality, t ′ 1 t 6 ∈ E but now, ( t 3 , t 2 , t ′ 1 , t 6 , t 7 ) induce a P 5 with special endpoint t 3 , which is a contradiction to Claim 3. Analogously, if t ′ 1 = t ′ 5 , it leads to the same contradiction. Thus, Claim 11 is shown.

In general, if t 2 does not completely color T 3 then we can add a possible coloring of T 3 which leads to a complete coloring of every neighbor T i of T 3 . Since G is P 9 -free, Case 2.2 appears only once in component K .

Thus, Lemma 3 is shown.

/negationslash

## 4 The Case N 4 = ∅

/negationslash

/negationslash

Recall A xy := { x, y } ∪ N 1 ∪ N 2 ∪ N 3 and N 5 = ∅ . In the case N 4 = ∅ , we show that one can check in polynomial time whether G has a d.i.m. M with xy ∈ M . Clearly, again in the case N 4 = , all the components of ∅ G S [ 2 ∪ N 3 ∪ N 4 ] can be independently colored.

Recall Observation 5; if t ∈ N 3 then t is an endpoint of a corresponding induced P 5 in { x, y } ∪ N 1 ∪ S 2 ∪ N 3 . If there is a P 5 ( t, a, b, c, d ) with endpoint t and four vertices a, b, c, d ∈ N 4 (such that only one of them, say a contacts t ) then t is the midpoint of a P 9 in G , which is a contradiction. Analogously, if there is a P 5 ( t, a, b, c, t ′ ) with t, t ′ ∈ N 3 such that t and t ′ are in distinct T i 's then t is the midpoint of a P 9 in G , which is a contradiction. This argument is used in some of the next proofs.

Proposition 1. If the colors of all vertices in G A [ xy ] are fixed then the colors of all vertices in N 4 are forced.

Proof. Let v ∈ N 4 and let w ∈ N 3 be a neighbor of v . Since by (7), every edge between N 3 and N 4 is xy -excluded, we have: If w is white then v is black, and if w is black then v is white.

Let K be a nontrivial component of G S [ 2 ∪ N 3 ∪ N 4 ]. Clearly, K can have several components in G S [ 2 ∪ N 3 ] which are connected by some N 4 -vertices. K can be feasibly colored (if there is no contradiction) by starting with a component in G S [ 2 ∪ N 3 ] or with a component in G N [ 4 ] which is part of K .

Recall (8) and (9) for the fact that after the Edge Reduction, there is no triangle between N 3 and N 4 with exactly one vertex in N 3 , and for every edge uv in G N [ 4 ], u and v have no common neighbor in N 3 . Moreover, for N 4 -vertices which are isolated in N 4 , we have:

$$\text{If } v \in N _ { 4 } \text{ with } N ( v ) \cap N _ { 4 } = \emptyset \text{ then } v \text{ is white.}$$

Thus, after the Vertex Reduction, we can assume that every vertex in N 4 has a neighbor in N 4 , i.e., every component in G N [ 4 ] has at least one edge.

Similarly, we have:

Claim 12. If v, w ∈ N 4 with vw ∈ E is an N 4 -isolated edge in G N [ 4 ] then vw is an xy -forced M -edge, i.e., v and w are black.

Proof. Let v, w ∈ N 4 with vw ∈ E such that v and w do not have any other neighbors in N 4 . Clearly, since vw ∈ E , at least one of v and w is black, say v is black. If w is white then v needs a black M -mate in N 4 since by (7), there is no M -edge between N 3 and N 4 . But since vw is N 4 -isolated, there is no such M -mate of v , i.e., w is black. Thus, Claim 12 is shown.

Thus, after the Edge Reduction, there is no such N 4 -isolated edge in N 4 .

By the way, there are possible contradictions: For instance, if for an N 4 -isolated edge vw v , or w contacts a black vertex in N 3 then there is no d.i.m. with xy ∈ M . Analogously, if vt ∈ E for t ∈ N 3 and wt ′ ∈ E for t ′ ∈ N 3 and tt ′ ∈ E (i.e., ( t, v, w, t ′ ) induce a C 4 ) then there is no d.i.m. with xy ∈ M .

Claim 13. If t ∈ T i , t ′ ∈ T j (possibly i = j ), and a, b, c ∈ N 4 induce a C 5 C = ( t, a, b, t , c ′ ) in G N [ 3 ∪ N 4 ] then ab is an xy -forced M -edge.

Proof. Let C = ( t, a, b, t , c ′ ) be a C 5 in G N [ 3 ∪ N 4 ]. Then the edges ta, tc, t b, t c ′ ′ are edges between N 3 and N 4 . By Observation 1 ( ), every i C 5 has exactly one M -edge, and by (7), no edge between N 3 and N 4 is in M . Thus, ab is an xy -forced M -edge, and Claim 13 is shown.

In general, for any C 5 in G N [ 3 ∪ N 4 ] with exactly one edge in G N [ 4 ], this edge is xy -forced as an M -edge. After the Edge Reduction step, we can assume that there is no such C 5 in G N [ 3 ∪ N 4 ] with exactly one edge in G N [ 4 ].

/negationslash

Corollary 3. If ab ∈ E for a, b ∈ N 4 and at ∈ E bt , ′ ∈ E for t, t ′ ∈ N 3 , t = t ′ , such that ( t, a, b, t ′ ) induce a P 4 in G then there is no common neighbor c ∈ N 4 of t and t ′ .

Proof. Suppose to the contrary that there is such a common neighbor c ∈ N 4 with tc ∈ E and t c ′ ∈ E . Then ac / E ∈ and bc / E ∈ since there are no triangles ( t, a, c ), ( t , b, c ′ ). But then C = ( t, a, b, t , c ′ ) induce a C 5 , which is a contradiction by Claim 13 and the Edge Reduction. Thus, Corollary 3 is shown.

Claim 14. If t ∈ T i and a, b, c ∈ N 4 induce a C 4 C = ( t, a, b, c ) then t is black and u t i is an xy -forced M -edge.

Proof. Let C = ( t, a, b, c ) be a C 4 with exactly one N 3 -vertex t . Suppose to the contrary that t is white. Then by Observation 1 ( ii ), a and c are black, b is white, and by (7), there are M -mates a ′ ∈ N 4 of a and c ′ ∈ N 4 of c , i.e., aa ′ ∈ M and cc ′ ∈ M . Since G is butterfly-free, b is nonadjacent to at least one vertex of { a , c ′ ′ } , say b is nonadjacent to c ′ without loss of generality by symmetry. By (8) and the Edge Reduction, tc ′ / E ∈ ; let t ′ ∈ N 3 be a neighbor of c ′ , i.e., t c ′ ′ ∈ E . Then t ′ is white (since cc ′ ∈ M ), i.e., t b ′ / E ∈ ; furthermore, by (7), t c ′ / E ∈ . Then, since ( t , c , c, b, a ′ ′ ) do not induce a P 5 (else by Observation 5, t ′ is the midpoint of a P 9 in G ), we have t a ′ ∈ E but now, C = ( t, a, t , c , c ′ ′ ) is a C 5 with exactly one edge in N 4 , namely cc ′ . By Claim 13 and the Edge Reduction, we have that there is no such C 5 , i.e., t is black and u t i is an xy -forced M -edge. Thus, Claim 14 is shown.

After the Edge Reduction step, we can assume that there is no such C 4 in G N [ 3 ∪ N 4 ].

## Corollary 4.

- ( ) i If ( a, b, c, d ) induce a P 4 in G N [ 4 ] with N 3 -neighbor t of a then ( t, a, b, c, d ) induce a C 5 in G N [ 3 ∪ N 4 ] .

/negationslash

- ( ii ) If ( a, b, c ) induce a P 3 in G N [ 4 ] with N 3 -neighbor t of a and t ′ of c (clearly, t = t ′ ) then either tt ′ ∈ E , i.e., ( t, a, b, c, t ′ ) induce a C 5 in G N [ 3 ∪ N 4 ] , or t, t ′ ∈ T i .

Claim 15. There is no P 3 ( a, b, c ) in G N [ 4 ] with white end-vertices a and c .

/negationslash

Proof. Suppose to the contrary that there is such a P 3 ( a, b, c ) in G N [ 4 ] with white endvertices a and c , and thus black vertex b . Let t a ∈ T i be an N 3 -neighbor of a , and let t c be an N 3 -neighbor of c . By Claim 14 and the Edge Reduction, t a c / E ∈ and t c a / E ∈ , i.e., t a = t c . Clearly, t a and t c are black, and thus, t c / T ∈ i (and there is no T j with t a , t c ∈ T j ). Moreover, t a c t / E ∈ since both of them are black (recall that by (7), there is no M -edge in N 3 ). But then ( t a , a, b, c, t c ) induce a P 5 , and it leads to a P 9 in G with midpoint t a , which is a contradiction. Thus, Claim 15 is shown.

Corollary 5. If vertex z in G N [ 4 ] has degree at least 3 in G N [ 4 ] then z is white.

Proof. Suppose to the contrary that there is a black vertex z in G N [ 4 ] with degree at least 3, say zz i ∈ E , 1 ≤ i ≤ 3. Without loss of generality, assume that z 1 is black. But then z 2 and z 3 are white, and thus, ( z , z, z 2 3 ) induce a P 3 with white end-vertices z , z 2 3 , which is a contradiction to Claim 15. Thus, Corollary 5 is shown.

Thus, after the Vertex Reduction, every vertex in a component of G N [ 4 ] has degree at most 2 in G N [ 4 ]. For every component D of G N [ 4 ], this leads to feasible colorings of D :

Claim 16. Every component D in G N [ 4 ] is either a P k , 3 ≤ k ≤ 8 , or a C k , k ∈ { 3 6 9 , , } , and D has at most three feasible colorings.

Proof. Recall that after the Vertex Reduction, every vertex in a component D of G N [ 4 ] has degree at most 2 in G N [ 4 ]. If D is cycle-free then, since D contains a P 3 (recall (10) and Claim 12) and G is P 9 -free, D is a P k , 3 ≤ k ≤ 8. If D contains a C k C then, since G is P 9 -free, k ≤ 9, and since every vertex in C has degree 2, C is no C 4 , C 5 , C 7 , C 8 , since every black vertex in C must have an M -mate in C . Thus, C is either a C 3 , C 6 , or C 9 . Clearly, for a C k , k ∈ { 3 6 9 , , } , say C = ( z , . . . , z 1 k ), there are three feasible colorings; for

example, in a C 9 , if z 1 is white then z 4 and z 7 are white and the remaining vertices are black, and similarly if z 2 is white or z 3 is white. For induced paths P k , 3 ≤ k ≤ 8, say P = ( z , . . . , z 1 k ), there are either one or two feasible colorings; if z 1 is white then z 2 and z 3 are black and thus z 4 is white etc. Thus, it leads to exactly one feasible coloring for P 4 , P 5 , P 7 , P 8 , and for exactly two feasible colorings for P 3 and P 6 . Thus, Claim 16 is shown.

Claim 17. Let ( a, b, c ) be a P 3 in G N [ 4 ] for a, b, c ∈ N 4 . If b is white then all N 3 -neighbors of a, b, c are in the same T i .

Proof. Let t a ∈ N 3 be the neighbor of a , and analogously, let t b , t c be the neighbors of b , c in N 3 . Without loss of generality, let t a ∈ T 1 . Clearly, t a b / E ∈ , t a c / E ∈ , and t c a / E ∈ , t c b / E ∈ . Since b is white, a and c are black, and there are black M -mates a ′ ∈ N 4 of a and c ′ ∈ N 4 of c (recall that by (7), there is no M -edge between N 3 and N 4 ). By Claim 16, a b / E ′ ∈ and c b ′ / E ∈ .

Now by Corollary 4 ( ), i t a c ′ ∈ E and t c a ′ ∈ E . Clearly, t a and t c are white, and thus, t a c t / E ∈ . Since ( t a , a, b, c, t c ) do not induce a P 5 with t c / T ∈ 1 (else it leads to a P 9 in G ), we have t c ∈ T 1 .

Suppose that t b / T ∈ 1 . Then, since ( t b , b, c, c , t ′ a ) do not induce a P 5 (else there is a P 9 in G with midpoint t a ), we have t b t a ∈ E , and analogously, since ( t b , b, a, a , t ′ c ) do not induce a P 5 , we have t b t c ∈ E but now, t b / T ∈ 1 contacts two vertices in T 1 , which is a contradiction (recall Lemma 1 ( v )). Thus, t b ∈ T 1 , and Claim 17 is shown.

Corollary 6. For a component D in G N [ 4 ] with P 3 ( a, b, c ) such that b is white, there are three N 3 -neighbors of D in the same T i such that every vertex of D contacts one of them.

Proof. If D is a P 5 ( a , a, b, c, c ′ ′ ) as in the proof of Claim 17 then clearly, there are three N 3 -neighbors of D in the same T i such that every vertex a , a, b, c, c ′ ′ contacts one of them. Clearly, D is P 9 -free. Now assume that there is a neighbor d ∈ N 4 of c ′ (recall that every vertex in D has degree at most 2). Clearly, d is white, dc / E ∈ and db / E ∈ . Let t b ∈ N 3 be a neighbor of vertex b . Since ( t b , b, c, c , d ′ ) do not induce a P 5 , by the discussion at the beginning of the section, we have t b d ∈ E . Accordingly, if e ∈ N 4 is a neighbor of d and t c ∈ N 3 is a neighbor of vertex c then, since ( t c , c, c , d, e ′ ) do not induce a P 5 , we have t c e ∈ E etc. Thus, Corollary 6 is shown.

Claim 18. Let D ,D 1 2 be two components in G N [ 4 ] and let a, b ∈ V ( D 1 ) with white vertex a and ab ∈ E as well as c, d ∈ V ( D 2 ) with cd ∈ E . Then c and d are colored black by the white vertex a .

Proof. Let t a ∈ T 1 be an N 3 -neighbor of a . Then t a is black, and all other vertices in T 1 are white. Let t c ∈ N 3 be a neighbor of c . Clearly, t a b / E ∈ and t c d / E ∈ , and ab, cd induce a 2 P 2 in G N [ 4 ]. If t c / T ∈ 1 , say t c ∈ T 2 , and t a t c / E ∈ then ( b, a, t a , u 1 ), ( d, c, t c , u 2 ), and the shortest path in N 1 ∪{ x, y } between u 1 and u 2 lead to a P 9 , which is a contradiction. Thus, either t c ∈ T 1 or t c t a ∈ E which implies that t c is white, and thus, c is black. Analogously, d is colored black by the white vertex a , and Claim 18 is shown.

Corollary 7. There is only one component in G N [ 4 ] .

Proof. Suppose to the contrary that there are two such components D ,D 1 2 in G N [ 4 ]. Clearly, by Claim 12 and the Edge Reduction, D 1 contains a white vertex a ; let ab ∈ E for a, b ∈ V ( D 1 ). As in the proof of Claim 18, let t a ∈ T 1 be an N 3 -neighbor of a which is black, and all other vertices in T 1 are white, and c and d are black for an edge cd ∈ E , c, d ∈ V ( D 2 ). Clearly, D 2 has at least three vertices; let e be a neighbor of c or d , say de ∈ E . Then e is white, and thus, an N 3 -neighbor t e of e is black, and thus, t e / T ∈ 1 and t a e t / E ∈ ; let t e ∈ T 2 . But now, ( b, a, t a , u 1 ), ( d, e, t e , u 2 ), and the shortest path in N 1 ∪ { x, y } between u 1 and u 2 lead to a P 9 , which is a contradiction. Thus, Corollary 7 is shown.

/negationslash

Let K be a nontrivial component of G S [ 2 ∪ N 3 ∪ N 4 ], and let Q ,. . . , Q 1 /lscript be the components of K in G S [ 2 ∪ N 3 ] and let D be the component of K in G N [ 4 ]. For each of the (at most three) feasible colorings of D , it leads to a partial coloring in every Q i since there is no contact between Q i and Q j , i = , and thus, there are contacts between j Q i and D . Then, as in Section 3, for every Q i , it can be independently checked in polynomial time whether Q i has a feasible coloring or a contradiction.

This finally shows:

Theorem 3. DIM is solvable in polynomial time for P 9 -free graphs.

## 5 Conclusion

In [9], it is shown that for every graph class of bounded clique-width, the DIM problem can be solved in polynomial time. However, there are many examples where the clique-width is unbounded but DIM is solvable in polynomial time; for example, the clique-width of P 9 -free graphs is unbounded. The complexity of DIM is still an open problem for many examples.

Acknowledgment. We are grateful to the anonymous referees for their helpful comments. The second author would like to witness that he just tries to pray a lot and is not able to do anything without that - ad laudem Domini.

## References

- [1] G. Bacs´ and Zs. Tuza, A characterization of graphs without long induced paths, o J. Graph Theory 14, 4 (1990) 455-464.
- [2] N. Biggs, Perfect codes in graphs, Journal of Combinatorial Theory, Series B 15 (1973) 289-296.
- [3] A. Brandst¨dt, C. Hundt, and R. Nevries, Efficient Edge Domination on Hole-Free graphs in Polya nomial Time, Conference Proceedings LATIN 2010, Lecture Notes in Computer Science 6034 (2010) 650-661.
- [4] A. Brandst¨dt and R. Mosca, Dominating Induced Matchings for a P 7 -Free Graphs in Linear Time, Algorithmica 68 (2014) 998-1018.
- [5] A. Brandst¨dt and R. Mosca, Finding Dominating Induced Matchings in a P 8 -Free Graphs in Polynomial Time, Algorithmica 77 (2017) 1283-1302.
- [6] A. Brandst¨dt a and R. Mosca, Dominating Induced Matchings in S 1 2 4 , , -Free Graphs, CoRR arXiv:1706.09301, 2017. Available online in Discrete Applied Math.
- [7] A. Brandst¨dt and R. Mosca, Finding Dominating Induced Matchings in a S 2 2 3 , , -Free Graphs, CoRR arXiv:1706.04894, 2017. Available online in Discrete Applied Math.

| [8]   | A. Brandst¨dt a and R. Mosca, Finding Dominating Induced Matchings in S 1 , 1 , 5 -Free Graphs, CoRR arXiv:1905.05582, 2019. Accepted for Discrete Applied Math.                         |
|-------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [9]   | D.M. Cardoso, N. Korpelainen, and V.V. Lozin, On the complexity of the dominating induced match- ing problem in hereditary classes of graphs, Discrete Applied Math. 159 (2011) 521-531. |
| [10]  | D.L. Grinstead, P.L. Slater, N.A. Sherwani, and N.D. Holmes, Efficient edge domination problems in graphs, Information Processing Letters 48 (1993) 221-228.                             |
| [11]  | A. Hertz, V.V. Lozin, B. Ries, V. Zamaraev, and D. de Werra, Dominating induced matchings in graphs containing no long claw, Journal of Graph Theory 88, no. 1 (2018) 18-39.             |
| [12]  | N. Korpelainen, V.V. Lozin, and C. Purcell, Dominating induced matchings in graphs without a skew star, J. Discrete Algorithms 26 (2014) 45-55.                                          |
| [13]  | C.L. Lu, M.-T. Ko, and C.Y. Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Math. 119 (2002) 227-250.                                            |
| [14]  | C.L. Lu and C.Y. Tang, Solving the weighted efficient edge domination problem on bipartite permu- tation graphs, Discrete Applied Math. 87 (1998) 203-211.                               |
Andreas Brandstädt Raffaele Mosca
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' \subseteq E$
is a {\em dominating induced matching} ({\em d.i.m.}) in $G$ if every edge in
$E$ is intersected by exactly one edge of $E'$. The \emph{Dominating Induced
Matching} (\emph{DIM}) problem asks for the existence of a d.i.m.\ in $G$. The
DIM problem is \NP-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.