Maximizing several cuts simultaneously

Simple item page
dc.creatorKuehn, Daniela
dc.creatorOsthus, Deryk
dc.date2005-03-21
dc.date.accessioned2026-07-07T05:18:08Z
dc.date.available2026-07-07T05:18:08Z
dc.descriptionConsider two graphs G_1 and G_2 on the same vertex set V and suppose that G_i has m_i edges. Then there is a bipartition of V into two classes A and B so that for both i=1,2 the number of edges between A and B in G_i is (1+o(1))m_i/2. This answers a question of Bollobas and Scott. We also prove results about partitions into more than two vertex classes.
dc.identifierhttps://arxiv.org/abs/math/0503403
dc.identifierhttp://arxiv.org/abs/math/0503403
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/74557
dc.subjectCombinatorics
dc.subject05C35; 05D40; 05C85
dc.titleMaximizing several cuts simultaneously
dc.typetext

Files

Collections

arXiv