The recognition of the class of indecomposable digraphs under low hemimorphy

Given a digraph G = ( V , A ) , the subdigraph of G induced by a subset X of V is denoted by G [ X ] . With each digraph G = ( V , A ) is associated its dual G ⋆ = ( V , A ⋆ ) defined as follows: for any x , y ∈ V , ( x , y ) ∈ A ⋆ if ( y , x ) ∈ A . Two digraphs G and H are hemimorphic if G is isomorphic to H or to H ⋆ . Given k > 0 , the digraphs G = ( V , A ) and H = ( V , B ) are k -hemimorphic if for every X ⊆ V , with | X | ≤ k , G [ X ] and H [ X ] are hemimorphic. A class C of digraphs is k -recognizable if every digraph k -hemimorphic to a digraph of C belongs to C . In another vein, given a digraph G = ( V , A ) , a subset X of V is an interval of G provided that for a , b ∈ X and x ∈ V − X , ( a , x ) ∈ A if and only if ( b , x ) ∈ A , and similarly for ( x , a ) and ( x , b ) . For example, 0̸ , { x } , where x ∈ V , and V 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.