D. Hartvigsen recently gave an algorithm to find a C4-free 2-factor in a bipartite graph and using this algorithm he proved several nice theorems. Now we give a simple inductive proof for a generalization of his Tutte-type theorem, and prove the corresponding Ore-type theorem as well. The proof follows the idea of the inductive proof for the Hall's theorem given by Halmos and Vaughn.
Bibtex entry:
AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n}, |
TITLE | = | {$C_4$-free 2-factors in bipartite graphs}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2001}, |
NUMBER | = | {TR-2001-13} |