Cutting two graphs simultaneously |
| |
Authors: | Viresh Patel |
| |
Affiliation: | Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, UK |
| |
Abstract: | Consider two graphs, and , on the same vertex set V, with and having edges for . We give a simple algorithm that partitions V into sets A and B such that and . We also show, using a probabilistic method, that if and belong to certain classes of graphs, (for instance, if and both have a density of at least 2/, or if and are both regular of degree at most with n sufficiently large) then we can find a partition of V into sets A and B such that for . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 19–32, 2008 |
| |
Keywords: | cuts |
|
|