Győri, Ervin and Kostochka, A. and McConvey, Andrew and Yager, Derrek (2016) Toward Żak's conjecture on graph packing. JOURNAL OF COMBINATORICS, 7 (23). pp. 307340. ISSN 21563527

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 > QA166QA166.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 