A list version of graph packing

Ervin Gyori, Alexandr Kostochka, Andrew McConvey, Derrek Yager

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)2178-2185
Number of pages8
JournalDiscrete Mathematics
Volume339
Issue number8
DOIs
StatePublished - Aug 6 2016

Keywords

  • Edge sum
  • Graph packing
  • List coloring
  • Maximum degree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'A list version of graph packing'. Together they form a unique fingerprint.

Cite this