Critically indecomposable graphs

An undirected graph G=(V,E)G=(V,E) with a specific subset X⊂VX⊂V is called XX-critical if GG and G(X)G(X), induced subgraph on XX, are indecomposable but G(V−{w})G(V−{w}) is decomposable for every w∈V−Xw∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191–205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)(n−2)-property, Theoretical Computer Science 132 (1994) 151–178], who deal with the case where XX is empty.We present several structural results for this class of graphs and show that in every XX-critical graph the vertices of V−XV−X can be partitioned into pairs (a1,b1),(a2,b2),…,(am,bm)(a1,b1),(a2,b2),…,(am,bm) such that G(V−{aj1,bj1,…,ajk,bjk})G(V−{aj1,bj1,…,ajk,bjk}) is also an XX-critical graph for arbitrary set of indices {j1,…,jk}{j1,…,jk}. These vertex pairs are called commutative elimination sequence  . If GG is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X)G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x1,y1),…,(xt,yt)(x1,y1),…,(xt,yt) such that xi,yi∈V−Xxi,yi∈V−X. As an application of the commutative elimination sequence of an XX-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X)G(X) to entire GG.