C4-free 2-factors in bipartite graphs

Zoltán Király


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-13}

Last modification: 10.9.2021. Please email your comments to Tamás Király!