Approximation Algorithms for the Vertex Bipartization Problem

摘要

To guarantee the optimal bipartite vertex coloring (bipar-tization) of a connected graph requires a coloring algorithm that is NP-complete, effectively preventing bipartization of even modest sized graphs. We present some approximation algorithms that run in polyno-mial time and lead to very good (but not necessarily optimal) colorings.