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 + m log n ) . Also G is shown to be 3-colorable if it is free from fully odd K 4 and G [ X ] is 3-colorable. The time complexity of the 3-coloring algorithm is O ( n ( n + m ) ) .