| Tartalmi leírás: |
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.
|
| Azonosító: |
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
|
