Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/103513
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.
Editor: 
Rights: fechado
Identifier DOI: 
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-33745630933&partnerID=40&md5=cea459d37be5c29af462e16d23905f0a
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.