Bipartitioning Problems on Graphs with Bounded Tree-Width

N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare

For an undirected graph G, we consider the following problems: given a fixed graph H, can we partition the vertices of G into two non-empty sets A and B such that neither the induc…