Please use this identifier to cite or link to this item:
|Type:||Artigo de evento|
|Title:||Packing Dicycle Covers In Planar Graphs With No K 5 - E Minor|
|Abstract:||We prove that the minimum weight of a dicycle is equal to the maximum number of disjoint dicycle covers, for every weighted digraph whose underlying graph is planar and does not have K 5 - e as a minor (K 5 - e is the complete graph on five vertices, minus one edge). Equality was previously known when forbidding K 4 as a minor, while an infinite number of weighted digraphs show that planarity does not guarantee equality. The result also improves upon results known for Woodall's Conjecture and the Edmonds-Giles Conjecture for packing dijoins. Our proof uses Wagner's characterization of planar 3-connected graphs that do not have K 5 - e as a minor. © Springer-Verlag Berlin Heidelberg 2006.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.