A sufficient condition for a hypergraph to have a Berge-$k$-factor

Abstract

For any graph (hypergraph) $G$ with vertex set $V$ and edge set $E$, we define its incidence bipartite graph $\mathcal{I}(G)$ as the bipartite graph with bipartition $(E,V)$, where an edge $e\in E$ is adjacent to a vertex $v\in V$ in $\mathcal{I}(G)$ if and only if $e$ is incident to $v$ in $G$. This representation allows all concepts and properties of $G$ to be reformulated in terms of those of $\mathcal{I}(G)$. In this paper, we investigate the notions of graph toughness and $k$-factors in bipartite graphs through this incidence perspective. As an application, our result implies the classic theorem of Enomoto, Jackson, Katerinis, and Saito: for any integer $k\ge 1$, a $k$-tough graph $G$ has a $k$-factor if $k|V(G)|$ is even and $|V(G)|\ge k+1$. Furthermore, we extend this result to hypergraphs, without requiring uniformity.

15pages