부산대학교 도서관

In a hypergraph $H$, an extended matching is a disjoint collection of hyperedges and pairs of nodes $(u, v)$ such that there exists a hyperedge $e$ with $u, v \in e$. In this paper, the authors prove that in a 3-uniform hypergraph $H$, there exists an extended matching covering the nodes of maximum degree in $H$. This result implies a conjecture of Y. C. Liang, which implies that 4-regular graphs are antimagic. The second main result of this paper states 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.