A list version of graph packing

Ervin Győri; Alexandr Kostochka; Andrew McConvey; Derrek Yager

paper

A list version of graph packing

arXiv:1501.02488

Abstract

We consider the following generalization of graph packing. Let $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ be graphs of order $n$ and $G_{3} = (V_{1} \cup V_{2}, E_{3})$ a bipartite graph. A bijection $f$ from $V_{1}$ onto $V_{2}$ is a list packing of the triple $(G_{1}, G_{2}, G_{3})$ if $uv \in E_{2}$ implies $f (u) f (v) \in / E_{2}$ and $v f (v) \in / E_{3}$ for all $v \in V_{1}$ . 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 $Δ (G_{1}) \leq n - 2, Δ (G_{2}) \leq n - 2, Δ (G_{3}) \leq n - 1$ , and $∣ E_{1} ∣ + ∣ E_{2} ∣ + ∣ E_{3} ∣ \leq 2 n - 3$ , then either $(G_{1}, G_{2}, G_{3})$ packs or is one of 7 possible exceptions. Hopefully, the concept of list packing will help to solve some problems on ordinary graph packing, as the concept of list coloring did for ordinary coloring.

10 pages, 4 figures