2025-11-10T03:06:56.403525

List Packing and Correspondence Packing of Planar Graphs

Cranston, Smith-Roberge
For a graph $G$ and a list assignment $L$ with $|L(v)|=k$ for all $v$, an $L$-packing consists of $L$-colorings $φ_1,\cdots,φ_k$ such that $φ_i(v)\neφ_j(v)$ for all $v$ and all distinct $i,j\in\{1,\ldots,k\}$. Let $χ^{\star}_{\ell}(G)$ denote the smallest $k$ such that $G$ has an $L$-packing for every $L$ with $|L(v)|=k$ for all $v$. Let $\mathcal{P}_k$ denote the set of all planar graphs with girth at least $k$. We show that (i) $χ^{\star}_{\ell}(G)\le 8$ for all $G\in \mathcal{P}_3$ and (ii) $χ^{\star}_{\ell}(G)\le 5$ for all $G\in \mathcal{P}_4$ and (iii) $χ^{\star}_{\ell}(G)\le 4$ for all $G\in \mathcal{P}_5$. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also construct outerplanar graphs $G$ such that $χ^{\star}_{\ell}(G)=4$, which matches the known upper bound $χ^{\star}_{\ell}(G)\le 4$ for all outerplanar graphs. Finally, we consider the analogue of $χ^{\star}_{\ell}$ for correspondence coloring, $χ^{\star}_c$. In fact, all bounds stated above for $χ^{\star}_{\ell}$ also hold for $χ^{\star}_c$.
academic

تعبئة القوائم والتعبئة المقابلة للرسوم البيانية المستوية

المعلومات الأساسية

  • معرّف الورقة: 2401.01332
  • العنوان: تعبئة القوائم والتعبئة المقابلة للرسوم البيانية المستوية
  • المؤلفون: دانيال دبليو كرانستون (جامعة فرجينيا كومنولث)، إيفلين سميث-روبرج (جورجيا تك)
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 6 ديسمبر 2024 (الإصدار الثالث من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2401.01332

الملخص

تدرس هذه الورقة مسائل تعبئة القوائم (list packing) والتعبئة المقابلة (correspondence packing) للرسوم البيانية المستوية. بالنسبة للرسم البياني GG والتخصيص القائمي LL، حيث ∣L(v)∣=k|L(v)|=k لجميع الرؤوس vv، تحتوي تعبئة LL على تلوينات LL متعددة ϕ1,⋯ ,ϕk\phi_1,\cdots,\phi_k بحيث لجميع vv والقيم المختلفة i,j∈{1,…,k}i,j\in\{1,\ldots,k\} لدينا ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v). دع χℓ⋆(G)\chi^{\star}_{\ell}(G) يمثل أصغر قيمة kk بحيث يكون لدى GG تعبئة LL لكل ∣L(v)∣=k|L(v)|=k. تثبت الورقة أن: (i) لجميع الرسوم البيانية المستوية GG ذات المحيط على الأقل 3 لدينا χℓ⋆(G)≤8\chi^{\star}_{\ell}(G)\leq 8؛ (ii) لجميع الرسوم البيانية المستوية GG ذات المحيط على الأقل 4 لدينا χℓ⋆(G)≤5\chi^{\star}_{\ell}(G)\leq 5؛ (iii) لجميع الرسوم البيانية المستوية GG ذات المحيط على الأقل 5 لدينا χℓ⋆(G)≤4\chi^{\star}_{\ell}(G)\leq 4. تنطبق هذه النتائج أيضاً على المعاملات المماثلة χc⋆\chi^{\star}_c للتلوين المقابل.

الخلفية البحثية والدافع

  1. المشكلة الأساسية: دراسة الحدود العليا لعدد تعبئة القوائم والتعبئة المقابلة للرسوم البيانية المستوية. التعبئة القائمية هي تعميم للتلوين القائمي، وتتطلب إيجاد عدة تلوينات قائمية منفصلة بشكل متبادل.
  2. أهمية المشكلة:
    • التلوين القائمي مشكلة كلاسيكية في نظرية الرسوم البيانية، بقيمة نظرية وتطبيقية واسعة
    • مسائل التعبئة هي تعميم طبيعي لمسائل التلوين، تدرس تحسين تخصيص الموارد
    • الرسوم البيانية المستوية كفئة مهمة، خصائص تلوينها ذات أهمية نظرية خاصة
  3. القيود الموجودة:
    • أثبت كامبي وآخرون في عام 2024 أن χc⋆(G)≤10\chi^{\star}_c(G)\leq 10 لجميع الرسوم البيانية المستوية GG
    • لكن هذا الحد نسبياً خشن ويتطلب تحسيناً إضافياً
    • يفتقر إلى تحليل دقيق للرسوم البيانية المستوية ذات المحيط المختلف
  4. الدافع البحثي:
    • تحسين الحدود المعروفة، خاصة المشكلة التي طرحها كامبي وآخرون
    • إنشاء علاقة دقيقة بين المحيط وعدد التعبئة
    • توفير إطار تحليل موحد للتلوين المقابل

المساهمات الأساسية

  1. تحسين كبير لحدود تعبئة الرسوم البيانية المستوية: تحسين χc⋆(G)≤10\chi^{\star}_c(G)\leq 10 إلى χc⋆(G)≤8\chi^{\star}_c(G)\leq 8
  2. إنشاء علاقة دقيقة بين المحيط وعدد التعبئة:
    • المحيط ≥4: χc⋆(G)≤5\chi^{\star}_c(G)\leq 5
    • المحيط ≥5: χc⋆(G)≤4\chi^{\star}_c(G)\leq 4 (أمثل)
  3. توفير إثبات تم التحقق منه يدوياً بالكامل: على عكس الأعمال المعاصرة، يتجنب التحقق الحاسوبي
  4. معالجة موحدة لتعبئة القوائم والتعبئة المقابلة: جميع النتائج تنطبق على كلا نوعي التعبئة
  5. إثبات الأمثلية في حالة المحيط ≥5: من خلال بناء أمثلة توضح أن الحد ضيق

شرح الطريقة

تعريف المهمة

تعبئة القوائم: بالنظر إلى الرسم البياني GG والتخصيص kk (كل رأس vv له ∣L(v)∣=k|L(v)|=k لوناً متاحاً)، ابحث عن kk تلوينات LL ϕ1,…,ϕk\phi_1,\ldots,\phi_k بحيث:

  1. كل ϕi\phi_i هو تلوين LL قانوني
  2. لأي رأس vv وi,ji,j مختلفة، لدينا ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v)

التعبئة المقابلة: تعريف مماثل، لكن باستخدام التلوين المقابل بدلاً من التلوين القائمي، مع قيود أقوى.

إطار العمل التقني الأساسي

1. طريقة الرسم البياني الثنائي المساعد

  • التعريف: بالنسبة للرأس vv والتعبئة الموجودة ϕ\phi، قم بإنشاء رسم بياني ثنائي مساعد HvH_v
  • الجزء A: يمثل kk لوناً
  • الجزء B: يمثل kk تلوينات ϕ1,…,ϕk\phi_1,\ldots,\phi_k
  • الحافات: iϕj∈E(H)i\phi_j \in E(H) إذا وفقط إذا كان يمكن تعيين ϕj(v)=i\phi_j(v)=i

2. تطبيق نظرية هول

استخدام نظرية هول للحكم على ما إذا كان الرسم البياني الثنائي يحتوي على تطابق مثالي:

  • العقبة: مجموعة X⊆AX \subseteq A تحقق ∣N(X)∣<∣X∣|N(X)| < |X|
  • الملاحظة الرئيسية: حجم العقبات في الرسم البياني الثنائي (s,t)(s,t) محدود

3. أدوات التحليل الهيكلي

القضية 5: إذا كان GG رسماً بيانياً ثنائياً (s,t)(s,t) وكانت هناك X⊆AX \subseteq A بحيث ∣X∣>∣N(X)∣|X| > |N(X)|، فإن t+1≤∣X∣≤s−tt+1 \leq |X| \leq s-t.

النتيجة 6: إذا كان χc⋆(G−v)≤k\chi^{\star}_c(G-v) \leq k و d(v)≤k/2d(v) \leq k/2، فإن χc⋆(G)≤k\chi^{\star}_c(G) \leq k.

استراتيجية الإثبات الرئيسية

1. حالة المحيط ≥4 (النظرية 12)

  • طريقة التفريغ: تخصيص شحنة أولية لكل رأس تساوي درجته
  • قواعد التفريغ: كل رأس درجة 3 يحصل على شحنة 1/31/3 من كل جار
  • التكوينات المحظورة:
    • لا يمكن أن تكون رؤوس الدرجة 3 متجاورة
    • لا توجد حافة vwvw بحيث d(v)=3d(v)=3 و d(w)≤4d(w) \leq 4
    • رؤوس الدرجة 5 متجاورة مع ثلاثة رؤوس درجة 3 على الأكثر

2. حالة المحيط ≥5 (النظرية 15)

استخدام تحليل أكثر دقة:

  • اللمة الرئيسية: كل رأس في رسم بياني ثنائي (4,2)(4,2) يرتبط بحافتين على الأقل موجودة في عامل 1
  • تحليل المسار: التركيز على معالجة المسارات xvyxvy المكونة من رؤوس درجة 3
  • تقنية إعادة التعبئة: تعديل تلوينات الرؤوس المجاورة لإنشاء مساحة توسع للرأس المستهدف

3. حالة الرسوم البيانية المستوية العامة (النظرية 19)

  • نظرية بوروديين الهيكلية: الرسم البياني المستوي مع δ(G)≥5\delta(G) \geq 5 يحتوي على مثلث uvwuvw بحيث d(u)+d(v)+d(w)≤17d(u)+d(v)+d(w) \leq 17
  • تحليل نوع العقبة: تعريف 4 أنواع من العقبات ومعالجة كل منها بشكل منفصل
  • إعادة تعبئة معقدة: قد تتطلب تعديل تلوينات رأسين في نفس الوقت

الإعداد التجريبي

هذه ورقة نظرية بحتة لا تتضمن التحقق التجريبي، وجميع النتائج يتم الحصول عليها من خلال إثبات رياضي صارم.

الابتكارات التقنية الأساسية

1. نظام تصنيف العقبات

تعريف 4 أنواع من العقبات في الرسم البياني الثنائي (8,3)(8,3):

  • النوع 1: ∣X∣=5|X|=5، ∣N(X)∣=3|N(X)|=3
  • النوع 2: ∣X∣=4|X|=4، ∣N(X)∣=3|N(X)|=3، مع وجود هيكل توسع محدد
  • النوع 3: مشابه للنوع 2 لكن هيكل التوسع مختلف
  • النوع 4: حالات ∣X∣=4|X|=4، ∣N(X)∣=3|N(X)|=3 التي لا تنتمي إلى الأنواع الثلاثة الأولى

2. إطار التحليل الموحد

من خلال اللمة 8، إنشاء تكافؤ بين التلوين القائمي والتلوين المقابل، مما يسمح بـ "تصحيح" الترتيبات على الهياكل الشجرية.

3. قيود الدرجة الدقيقة

استخدام صيغة أويلر لإنشاء العلاقة بين المحيط ومتوسط الدرجة:

  • الرسم البياني المستوي ذو المحيط gg بمتوسط درجة <2g/(g−2)< 2g/(g-2)
  • المحيط 4: متوسط درجة <4< 4
  • المحيط 5: متوسط درجة <10/3< 10/3

النتائج الرئيسية

بيان النظريات

  1. النظرية 1: χc⋆(G)≤8\chi^{\star}_c(G) \leq 8 لجميع الرسوم البيانية المستوية GG
  2. النظرية 2: χc⋆(G)≤5\chi^{\star}_c(G) \leq 5 لجميع الرسوم البيانية المستوية GG ذات المحيط ≥4
  3. النظرية 3: χc⋆(G)≤4\chi^{\star}_c(G) \leq 4 لجميع الرسوم البيانية المستوية GG ذات المحيط ≥5، وهذا الحد أمثل

الأمثلية

من خلال أمثلة الحلقات CkC_k (k≥3k \geq 3) إثبات:

  • χℓ⋆(Ck)=3<4=χc⋆(Ck)\chi^{\star}_\ell(C_k) = 3 < 4 = \chi^{\star}_c(C_k)
  • يوضح أن التعبئة المقابلة أصعب من تعبئة القوائم
  • الحد 4 في حالة المحيط ≥5 ضيق

الأعمال ذات الصلة

  1. كامبي وآخرون (2024): أول دراسة منهجية لمسائل التعبئة، إثبات χc⋆(G)≤10\chi^{\star}_c(G) \leq 10
  2. الأعمال المعاصرة: العمل المستقل لكامبي وكامز فان باتنبرج وتشو إثبات النتائج نفسها لكن يعتمد على التحقق الحاسوبي
  3. نظرية التلوين الكلاسيكية: مبنية على الأعمال الكلاسيكية لهيوود وريجل-يونجز وآخرين حول تلوين الرسوم البيانية على الأسطح
  4. التلوين المقابل: الإطار النظري الذي أنشأه دفوراك-بوستل وآخرون

الاستنتاج والمناقشة

الاستنتاجات الرئيسية

  1. تحسين كبير لحدود عدد تعبئة الرسوم البيانية المستوية
  2. إنشاء علاقة دقيقة بين المحيط وعدد التعبئة
  3. توفير طريقة إثبات بناءة بالكامل
  4. معالجة موحدة لتعبئة القوائم والتعبئة المقابلة

القيود

  1. الإثبات معقد تقنياً، يتضمن تحليل حالات واسع
  2. لم يتم حل المشكلة للرسوم البيانية على الأسطح العامة
  3. الأمثلية لبعض الحدود لم تُحدد بالكامل بعد

الاتجاهات المستقبلية

تقترح الورقة 6 مسائل مفتوحة:

  1. تحديد القيم الدقيقة لـ χℓ⋆(P3)\chi^{\star}_\ell(\mathcal{P}_3) و χℓ⋆(P4)\chi^{\star}_\ell(\mathcal{P}_4)
  2. دراسة عدد التعبئة لفئات الرسوم البيانية ذات متوسط الدرجة المحدود
  3. مسألة التعبئة للرسوم البيانية المستوية الثنائية
  4. عدد التعبئة للرسوم البيانية على الأسطح العامة
  5. العلاقة مع عدد هيوود
  6. عدد التعبئة للرسوم البيانية الخالية من الرسوم البيانية الكاملة

التقييم المتعمق

المميزات

  1. مساهمة نظرية كبيرة: تحسين كبير لحدود مشكلة مهمة
  2. ابتكار الطريقة: تصنيف العقبات والإطار التحليلي الموحد له أهمية عامة
  3. إثبات كامل: تجنب التحقق الحاسوبي، جميع الإثباتات قابلة للتحقق يدوياً
  4. النتائج أمثل: حالة المحيط ≥5 تحقق الحد الأمثل
  5. الكتابة واضحة: التفاصيل التقنية منظمة بشكل جيد، الأمثلة تساعد الفهم

أوجه القصور

  1. الإثبات معقد: الكثير من التفاصيل التقنية وتحليل الحالات
  2. قابلية التعميم: وضوح تطبيق الطريقة على فئات رسوم بيانية أخرى غير واضح
  3. التعقيد الحسابي: لم تتم مناقشة مسائل التعقيد الحسابي

التأثير

  1. القيمة النظرية: تقدم تطور نظرية تلوين الرسوم البيانية
  2. قيمة الطريقة: قد تكون الأدوات التقنية قابلة للتطبيق على مسائل أخرى
  3. المسائل المفتوحة: المسائل المقترحة توفر اتجاهات للبحث اللاحق

السيناريوهات المعمول بها

  1. تجنب الصراعات في تخصيص الموارد
  2. تخصيص الطيف والتلوين الشبكي
  3. مسائل الجدولة مع القيود
  4. مسائل التعبئة في التحسين التوافقي

المراجع

تستشهد الورقة بـ 20 مرجعاً مهماً، بما في ذلك:

  • النتائج الكلاسيكية لبوروديين حول هيكل الرسوم البيانية المستوية
  • العمل الرائد لكامبي وآخرين حول مسائل التعبئة
  • نظرية دفوراك-بوستل حول التلوين المقابل
  • النظرية الكلاسيكية لهيوود حول تلوين الرسوم البيانية على الأسطح

تقدم هذه الورقة مساهمة مهمة في الرياضيات التوافقية، خاصة في نظرية تلوين الرسوم البيانية. من خلال تقنيات ماهرة، تحسن بشكل كبير حدود مسألة التعبئة للرسوم البيانية المستوية، وتضع أساساً متيناً لمزيد من التطور في هذا المجال.