Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76735
Type: Artigo de periódico
Title: Tutte's 3-flow conjecture and matchings in bipartite graphs
Author: da Silva, CN
Dahab, R
Abstract: Tutte's 3-flow conjecture is equivalent to the assertion that there exists an orientation of the edges of a 4-edge-connected, 5-regular graph G for which the out-flow at each vertex is +3 or -3. The existence of one such orientation of the edges implies the existence of an equipartition of the vertices of G that separates the two possible types of vertices. Such an equipatition is called mod 3-orientable. We give necessary and sufficient conditions for the existence of mod 3-orientable equipartitions in general 5-regular graphs, in terms of (i) a perfect matching of a bipartite graph derived from the equipartition and (ii) the sizes of cuts in G. Also, we give a polynomial time algorithm for testing whether an equipartition of a 5-regular graph is mod 3-orientable.
Country: Canadá
Editor: Charles Babbage Res Ctr
Rights: fechado
Date Issue: 2005
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000230694000006.pdf162.17 kBAdobe PDFView/Open


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