کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647001 1342321 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A list version of graph packing
ترجمه فارسی عنوان
نسخه فهرست بسته بندی گراف
کلمات کلیدی
بسته بندی گراف، حداکثر درجه، مجموع لبه، فهرست رنگ آمیزی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We consider the following generalization of graph packing. Let G1=(V1,E1)G1=(V1,E1) and G2=(V2,E2)G2=(V2,E2) be graphs of order nn and G3=(V1∪V2,E3)G3=(V1∪V2,E3) a bipartite graph. A bijection ff from V1V1 onto V2V2 is a list packing   of the triple (G1,G2,G3)(G1,G2,G3) if uv∈E1uv∈E1 implies f(u)f(v)∉E2f(u)f(v)∉E2 and for all v∈V1v∈V1, vf(v)∉E3vf(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Δ(G1)≤n−2,Δ(G2)≤n−2,Δ(G3)≤n−1, and |E1|+|E2|+|E3|≤2n−3|E1|+|E2|+|E3|≤2n−3, then either (G1,G2,G3)(G1,G2,G3) packs or is one of 7 possible exceptions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 8, 6 August 2016, Pages 2178–2185
نویسندگان
, , , ,