REAL

Toward Żak's conjecture on graph packing

Győri, Ervin and Kostochka, A. and McConvey, Andrew and Yager, Derrek (2016) Toward Żak's conjecture on graph packing. JOURNAL OF COMBINATORICS, 7 (2-3). pp. 307-340. ISSN 2156-3527

[img]
Preview
Text
packing2.pdf

Download (440kB) | Preview

Abstract

Two graphs G1=(V1,E1) and G2=(V2,E2), each of order n, pack if there exists a bijection f from V1 onto V2 such that uv∈E1 implies f(u)f(v)∉E2. In 2014, \.{Z}ak proved that if Δ(G1),Δ(G2)≤n−2 and |E1|+|E2|+max{Δ(G1),Δ(G2)}≤3n−96n3/4−65, then G1 and G2 pack. In the same paper, he conjectured that if Δ(G1),Δ(G2)≤n−2, then |E1|+|E2|+max{Δ(G1),Δ(G2)}≤3n−7 is sufficient for G1 and G2 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 Δ(G1),Δ(G2)≤n−2 and |E1|+|E2|+max{Δ(G1),Δ(G2)}≤3n−C, then G1 and G2 pack. In order to facilitate induction, we prove a stronger result on list packing.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 03 Jan 2017 14:33
Last Modified: 03 Jan 2017 14:33
URI: http://real.mtak.hu/id/eprint/44291

Actions (login required)

Edit Item Edit Item