Some Algorithms on Conditionally Critical Indecomposable Graphs

Let X be a subset of vertices of an undirected graph G=(V,E). G is X-critical if it is indecomposable and its induced subgraph on X vertices is also indecomposable, but every induced subgraphs on V−{w} is decomposable for w∈V−X. We present an algorithm to construct an elimination sequence on these graphs preserving critical indecomposability. We also consider two algorithmic problems over X-critical graphs: perfect matching and 3-coloring. It is shown that if a perfect matching for X exists then the same exists for G and it can be computed in O(n+mlogn). Also G is shown to be 3-colorable if it is free from fully odd K4 and G[X] is 3-colorable. The time complexity of the 3-coloring algorithm is O(n(n+m)).