Decomposing Dense Bipartite Graphs into 4-Cycles

  • Nicholas Cavenagh
Keywords: Graph decomposition, extremal graph theory

Abstract

Let $G$ be an even bipartite graph with partite sets $X$ and $Y$ such that $|Y|$ is even and the minimum degree of a vertex in $Y$ is at least $95|X|/96$. Suppose furthermore that the number of edges in $G$ is divisible by $4$. Then $G$ decomposes into 4-cycles.
Published
2015-02-25
Article Number
P1.50