2017/03/15 by Wouter Cames van Batenburg, Ross J. Kang, van Batenburg, Wouter Cames +1
Computer Science · Mathematics · #05C35 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1703.05149
openalex publication_date 2017/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two graphs G1 and G2 on n vertices are said to 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 (Δ(G1)+1) (Δ(G2)+1) ≤ n+1, then G1 and G2 pack. We consider the validity of this assertion under the additional assumptions that neither G1 nor G2 contain a 4-, 6- or 8-cycle, and that Δ(G1) or Δ(G2) is large enough (≥ 940060).