Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514575 | Electronic Notes in Discrete Mathematics | 2005 | 5 Pages |
Abstract
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)).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Chandan K. Dubey, Shashank K. Mehta,