@techreport{TR-IC-01-09,
number = {IC-01-09},
author = {Cândida Nunes da Silva and Ricardo Dahab},
title = {Tutte's 3-flow Conjecture and Matchings in Bipartite Graphs},
month = {August},
year = {2001},
institution = {Institute of Computing, University of Campinas},
note = {In English, 11 pages.
\par\selectlanguage{english}\textbf{Abstract}
Tutte's 3-flow conjecture is restated as the problem of finding 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 induced
equipartition of the vertices of $G$ 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 size of cuts in $G$. Also, we give a
polynomial time algorithm for testing whether an equipartition is mod
3-orientable.
}
}