A list version of graph packing

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)

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.

Recommendations

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)