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”.
Publisher Copyright:
© 2016 Elsevier B.V. All rights reserved.
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
SN - 0012-365X
VL - 339
SP - 2178
EP - 2185
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 8
ER -