Covering Multigraphs With Bipartite Graphs
ABSTRACT Hansel's lemma states , where is a collection of bipartite graphs covering all the edges of . We generalize this lemma to the corresponding multigraph covering problem and the graphon covering problem. We also prove an upper bound on which shows that our generalization is asymptotically tight in some sense.
Authors
- Hyun-Woo Lee (ORCID: https://orcid.org/0000-0001-8557-2099)
- Jaehoon Kim (ORCID: https://orcid.org/0000-0002-1411-4186)
Institutions
- Korea Advanced Institute of Science and Technology (KR)
Publication Details
- Journal
- Journal of Graph Theory
- Published
- 2026-11-13
- DOI
- https://doi.org/10.1002/jgt.70154
- Citations
- 3
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 1.87
Funders
- POSCO TJ Park Foundation
- National Research Foundation
- National Research Foundation of Korea
- Institute for Basic Science
- Ministry of Science and ICT, South Korea