TY - JOUR

T1 - A list version of graph packing

AU - Gyori, Ervin

AU - Kostochka, Alexandr

AU - McConvey, Andrew

AU - Yager, Derrek

N1 - Funding Information:
The authors would like to thank Gexin Yu and the referees for helpful comments. The first author’s research was supported in part by OTKA Grants 78439 and 101536 . The second author’s research was supported in part by NSF grant DMS-1266016 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research . The third author gratefully acknowledges support from the Campus Research Board, University of Illinois . The fourth author acknowledges support from National Science Foundation grant DMS 08-38434 “EMSW21-MCTP: Research Experience for Graduate Students”.

PY - 2016/8/6

Y1 - 2016/8/6

N2 - We consider the following generalization of graph packing. Let G1=V1,E1) and G2=(V2,E2) be graphs of order n and G3=(V1 ∪ V2, E3)a bipartite graph. A bijection f from V1 onto V2 is a list packing of the triple (G1, G2, G3) if uv ∈ E1 implies f(u)f(v) ∉ E2 and for all v ∈ V1 vf(v) ∉ E3. We extend the classical results of Sauer and Spencer and Bollobás and Eldridge on packing of graphs with small sizes or maximum degrees to the setting of list packing. In particular, we extend the well-known Bollobás-Eldridge Theorem, proving that if Δ(G1)≤n-2,Δ(G2)≤n-2,Δ(G3)≤n-1, and |E1|+|E2|+|E3|≤2n-3, then either (G1, G2, G3) packs or is one of 7 possible exceptions.

AB - We consider the following generalization of graph packing. Let G1=V1,E1) and G2=(V2,E2) be graphs of order n and G3=(V1 ∪ V2, E3)a bipartite graph. A bijection f from V1 onto V2 is a list packing of the triple (G1, G2, G3) if uv ∈ E1 implies f(u)f(v) ∉ E2 and for all v ∈ V1 vf(v) ∉ E3. We extend the classical results of Sauer and Spencer and Bollobás and Eldridge on packing of graphs with small sizes or maximum degrees to the setting of list packing. In particular, we extend the well-known Bollobás-Eldridge Theorem, proving that if Δ(G1)≤n-2,Δ(G2)≤n-2,Δ(G3)≤n-1, and |E1|+|E2|+|E3|≤2n-3, then either (G1, G2, G3) packs or is one of 7 possible exceptions.

KW - Edge sum

KW - Graph packing

KW - List coloring

KW - Maximum degree

UR - http://www.scopus.com/inward/record.url?scp=84964579420&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84964579420&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.03.001

DO - 10.1016/j.disc.2016.03.001

M3 - Article

AN - SCOPUS:84964579420

VL - 339

SP - 2178

EP - 2185

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 8

ER -