Cutting two graphs simultaneously
Viresh S. Patel · Journal of Graph Theory · 2007
Abstract Consider two graphs, $G_1$ and $G_2$ , on the same vertex set V, with $|V|= n$ and $G_{i}$ having $m_{i}$ edges for $i = 1,2$ . We give a simple algorithm that partitions V into sets A and B such that $e_{{G}_{1}}(A,B) \geq m_{1}/2$ and $e_{G_{2}}(A,B) \geq m_{2}/2 - \Delta (G_{2})/2$ . We also show, using a probabilistic method, that if $G_1$ and $G_2$ belong to certain classes of graphs, (for instance, if $G_1$ and $G_2$ both have a density of at least 2/, or if $G_1$ and $G_2$ are both regular of degree at most $(n/16) - 6$ with n sufficiently large) then we can find a partition of V into sets A and B such that $e_{G_{i}}(A,B) \geq m_{i}/2$ for $i = 1,2$ . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 19–32, 2008