Output details

Linear Balanceable and Subcubic Balanceable Graphs

<13>Balanced matrices (or bipartite graphs) have been much studied because of their important polyhedral properties. Their known decomposition (from early 90s) gave a recognition algorithm, but using it to obtain other results for this class proved difficult. Here, we develop deep general machinery (involving a radically new technique for obtaining extreme decomposition for star cutsets, and extreme 2-join decomposition result from [Vušković2]) to obtain a remarkably simple proof of C&R conjecture for linear balanced bipartite graphs, and other cases. Mentioned cutsets are common in decompositions of hereditary graph classes, so developed techniques are bound to be of further use.