Decomposing Dense Bipartite Graphs into 4-Cycles

Nicholas Cavenagh

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.

Keywords


Graph decomposition; extremal graph theory

Full Text: PDF