Toward Żak's conjecture on graph packing

Abstract: Two graphs

G_{1} = (V_{1}, E_{1})

and

G_{2} = (V_{2}, E_{2})

, each of order

n

, pack if there exists a bijection

f

from

V_{1}

onto

V_{2}

such that

u v i n E_{1}

implies

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

. In 2014, .{Z}ak proved that if

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

and

| E_{1} | + | E_{2} | + m a x D e l t a (G_{1}), D e l t a (G_{2}) l e q 3 n - 96 n^{3 / 4} - 65

, then

G_{1}

and

G_{2}

pack. In the same paper, he conjectured that if

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

, then

| E_{1} | + | E_{2} | + m a x D e l t a (G_{1}), D e l t a (G_{2}) l e q 3 n - 7

is sufficient for

G_{1}

and

G_{2}

to pack. We prove that, up to an additive constant, .{Z}ak's conjecture is correct. Namely, there is a constant

C

such that if

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

and

| E_{1} | + | E_{2} | + m a x D e l t a (G_{1}), D e l t a (G_{2}) l e q 3 n - C

, then

G_{1}

and

G_{2}

pack. In order to facilitate induction, we prove a stronger result on list packing.

Recommendations

Cited In (4)

This page was built for publication: Toward Żak's conjecture on graph packing