A list version of graph packing
  • Metaadatok
Tartalom: http://real.mtak.hu/44188/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published

Type = Article
Cím:
A list version of graph packing
Létrehozó:
Győri, Ervin
Kostochka, A.
McConvey, A.
Yager, D.
Kiadó:
North-Holland Publishing Company
Dátum:
2016
Téma:
QA Mathematics / matematika
QA166-QA166.245 Graphs theory / grĂĄfelmĂŠlet
Tartalmi leírás:
We consider the following generalization of graph packing. Let G1=V1,E1) and G2=(V2,E2) be graphs of order n and G3=(V1 ∪ V2, E3)a bipartite graph. A bijection f from V1 onto V2 is a list packing of the triple (G1, G2, G3) if uv ∈ E1 implies f(u)f(v) ∉ E2 and for all v ∈ V1 vf(v) ∉ E3. We extend the classical results of Sauer and Spencer and Bollobá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ás-Eldridge Theorem, proving that if Δ(G1)≤n-2,Δ(G2)≤n-2,Δ(G3)≤n-1, and |E1|+|E2|+|E3|≤2n-3, then either (G1, G2, G3) packs or is one of 7 possible exceptions. © 2016 Elsevier B.V. All rights reserved.
Nyelv:
angol
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Győri, Ervin and Kostochka, A. and McConvey, A. and Yager, D. (2016) A list version of graph packing. DISCRETE MATHEMATICS, 339 (8). pp. 2178-2185. ISSN 0012-365X
Kapcsolat:
MTMT:3118497; doi:10.1016/j.disc.2016.03.001