Cutting two graphs simultaneously |
| |
| Authors: | Viresh Patel |
| |
| Institution: | 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 |
|
|
