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
Author: Lee O.
Williams A.
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.
Rights: fechado
Identifier DOI: 
Date Issue: 2006
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-33745630933.pdf491.73 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.