Artículos de revistas
Tutte's 3-flow conjecture and matchings in bipartite graphs
Registro en:
Ars Combinatoria. Charles Babbage Res Ctr, v. 76, n. 83, n. 95, 2005.
0381-7032
WOS:000230694000006
Autor
da Silva, CN
Dahab, R
Institución
Resumen
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. 76 83 95