The recognition of the class of indecomposable digraphs under low hemimorphy

Given a digraph G=(V,A)G=(V,A), the subdigraph of GG induced by a subset XX of VV is denoted by G[X]G[X]. With each digraph G=(V,A)G=(V,A) is associated its dual G⋆=(V,A⋆)G⋆=(V,A⋆) defined as follows: for any x,y∈Vx,y∈V, (x,y)∈A⋆(x,y)∈A⋆ if (y,x)∈A(y,x)∈A. Two digraphs GG and HH are hemimorphic if GG is isomorphic to HH or to H⋆H⋆. Given k>0k>0, the digraphs G=(V,A)G=(V,A) and H=(V,B)H=(V,B) are kk-hemimorphic if for every X⊆VX⊆V, with |X|≤k|X|≤k, G[X]G[X] and H[X]H[X] are hemimorphic. A class CC of digraphs is kk-recognizable if every digraph kk-hemimorphic to a digraph of CC belongs to CC. In another vein, given a digraph G=(V,A)G=(V,A), a subset XX of VV is an interval of GG provided that for a,b∈Xa,b∈X and x∈V−Xx∈V−X, (a,x)∈A(a,x)∈A if and only if (b,x)∈A(b,x)∈A, and similarly for (x,a)(x,a) and (x,b)(x,b). For example, 0̸0̸, {x}{x}, where x∈Vx∈V, and VV are intervals called trivial. A digraph is indecomposable if all its intervals are trivial. We characterize the indecomposable digraphs which are 3-hemimorphic to a non-indecomposable digraph. It follows that the class of indecomposable digraphs is 4-recognizable.