A list version of graph packing

DOI10.1016/J.DISC.2016.03.001zbMATH Open1337.05086arXiv1501.02488OpenAlexW1508505492MaRDI QIDQ284763FDOQ284763

Authors: Alexandr Kostochka, Andrew McConvey, Derrek Yager, Ervin Győri

Publication date: 18 May 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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} c u p 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

u v i n E_{2}

implies

f (u) f (v) o t i n E_{2}

and

v f (v) o t i n E_{3}

for all

v i n V_{1}

. We extend the classical results of Sauer and Spencer and Bollob'{a}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'{a}s--Eldridge Theorem, proving that if

D e l t a (G_{1}) l e q n - 2, D e l t a (G_{2}) l e q n - 2, D e l t a (G_{3}) l e q n - 1

, and

| E_{1} | + | E_{2} | + | E_{3} | l e q 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.

Full work available at URL: https://arxiv.org/abs/1501.02488

Recommendations

zbMATH Keywords

list coloring maximum degree edge sum graph packing

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

Cited In (3)

This page was built for publication: A list version of graph packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284763)