A note on V-free 2-matchings
Kristóf Bérczi, Attila Bernáth, Máté Vizer · ELTE Digital Institutional Repository (EDIT) (Eötvös Loránd University) · 2015
Motivated by a conjecture of Liang, we introduce a restricted path packing problem in bipartite graphs that we call a V-free 2-matching. We verify the conjecture through a weakening of the hypergraph matching problem. We close the paper by showing that it is NP-complete to decide whether one of the color classes of a bipartite graph can be covered by a V-free 2-matching. © 2016, Australian National University. All rights reserved.