Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||Tutte's 3-flow conjecture and matchings in bipartite graphs|
|Author:||da Silva, CN|
|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.|
|Editor:||Charles Babbage Res Ctr|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.