bipartization

plural bipartizations

1. mathematicsThe removal of vertices from a graph in order to make it bipartite

   1 more example

   We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of more general XOR-d games to the identification of specific cycles in the graph.

   2015, Piotr Gnaciński, Monika Rosicka, Ravishankar Ramanathan, Karol Horodecki, Michał Horodecki, Paweł Horodecki, Simone Severini, “Linear game non-contextuality and Bell inequalities - a graph-theoretic approach”, in arXiv