2016/05/18 by van Batenburg, Wouter Cames, Kang, Ross J.
#05C35 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1605.05599
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 (Δ1(G)+1) (Δ2(G)+1) ≤ n+1, then G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2 has bounded codegree. In particular, we prove for all t ≥ 2 that, if G1 contains no copy of the complete bipartite graph K2,t and Δ1 > 17 t ⋅ Δ2, then (Δ1(G)+1) (Δ2(G)+1) ≤ n+1 implies that G1 and G2 pack. We also provide a mild improvement if moreover G2 contains no copy of the complete tripartite graph K1,1,s, s≥ 1.