The Bollobás-Eldridge-Catlin conjecture for even girth at least $10$

Wouter Cames van Batenburg; Ross J. Kang

paper

The Bollobás-Eldridge-Catlin conjecture for even girth at least $10$

arXiv:1703.05149

Abstract

Two graphs $G_{1}$ and $G_{2}$ on $n$ vertices are said to \textit{pack} if there exist injective mappings of their vertex sets into $[n]$ such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that, if $(Δ (G_{1}) + 1) (Δ (G_{2}) + 1) \leq n + 1$ , then $G_{1}$ and $G_{2}$ pack. We consider the validity of this assertion under the additional assumptions that neither $G_{1}$ nor $G_{2}$ contain a $4$ -, $6$ - or $8$ -cycle, and that $Δ (G_{1})$ or $Δ (G_{2})$ is large enough ( $\geq 940060$ ).

10 pages, 2 figures

The Bollobás-Eldridge-Catlin conjecture for even girth at least 10

Abstract

The Bollobás-Eldridge-Catlin conjecture for even girth at least $10$