2025-11-16T11:46:12.516239

Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

Balaji, Khazhinsky, Liu et al.
Odd coloring is a variant of proper coloring and has received wide attention. We study the list-coloring version of this notion in this paper. We prove that if $G$ is a graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, and 6 such that no 5-cycles share an edge, then for every function $L$ that assigns each vertex of $G$ a set $L(v)$ of size 5, there exists a proper coloring that assigns each vertex $v$ of $G$ an element of $L(v)$ such that for every non-isolated vertex, some color appears an odd number of times on its neighborhood. In particular, every graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, 6, and 8 is odd 5-choosable. The number of colors in these results are optimal, and there exist graphs embeddable in those surfaces of girth 6 requiring six or seven colors.
academic

تلوين القوائم الفردي للرسوم البيانية ذات جنس أويلر الصغير بدون دورات قصيرة من أنواع محددة

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

  • معرّف الورقة: 2508.15255
  • العنوان: Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
  • المؤلفون: Rishi Balaji, Victoria Khazhinsky, Chun-Hung Liu, Kevin Qin
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 14 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2508.15255

الملخص

تدرس هذه الورقة نسخة تلوين القوائم من التلوين الفردي للرسوم البيانية. تثبت النتائج الرئيسية أنه إذا كان الرسم البياني G قابلاً للتضمين في الطارة أو زجاجة كلاين، وخالياً من الدورات بأطوال 3 و4 و6، وليس لديه دورتان بطول 5 تشتركان في حافة، فإنه لكل دالة تخصص مجموعة ألوان بحجم 5 لكل رأس، يوجد تلوين مناسب بحيث يظهر لون معين عدداً فردياً من المرات في الحي المجاور لكل رأس غير معزول. على وجه الخصوص، كل رسم بياني قابل للتضمين في الطارة أو زجاجة كلاين وخالٍ من الدورات بأطوال 3 و4 و6 و8 هو فردي 5-قابل للاختيار. تُظهر الدراسة أن عدد الألوان في هذه النتائج هو الأمثل.

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

تعريف المشكلة

  1. مشكلة التلوين الفردي: التلوين الفردي هو متغير من التلوين المناسب، يتطلب أن يظهر لون واحد على الأقل عدداً فردياً من المرات في الحي المجاور لكل رأس غير معزول
  2. تلوين القوائم: لكل رأس قائمة بالألوان المتاحة، ويجب أن يختار التلوين الألوان من القوائم الخاصة به
  3. الرسوم البيانية المضمنة على السطوح: دراسة خصائص التلوين للرسوم البيانية القابلة للتضمين على سطوح محددة (الطارة، زجاجة كلاين)

أهمية البحث

  • مفهوم التلوين الفردي، على الرغم من أنه جديد نسبياً (تم تقديمه عام 2022 بواسطة Petruševski و Škrekovski)، قد جذب اهتماماً واسعاً
  • يجمع بين مفهومين مهمين في نظرية الرسوم البيانية: التضمين على السطوح والبنية الدورية المقيدة
  • له أهمية كبيرة في فهم سلوك نظرية تلوين الرسوم البيانية تحت القيود الطوبولوجية

حدود البحث الحالي

  • يحتقن Petruševski و Škrekovski أن كل رسم بياني مستوٍ هو فردي 5-قابل للتلوين، لكن أفضل نتيجة حالية هي فردي 8-قابل للتلوين
  • بالنسبة للرسوم البيانية على سطوح أكثر عمومية، النتائج المعروفة أقل
  • دراسة نسخة تلوين القوائم من التلوين الفردي نادرة جداً

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

  1. النظرية الرئيسية: إثبات أن الرسوم البيانية القابلة للتضمين في الطارة أو زجاجة كلاين والمستوفية لشروط دورية محددة هي فردية 5-قابلة للاختيار
  2. نتائج الأمثلية: إثبات أن عدد الألوان المطلوب 5 هو الأمثل، مع وجود أمثلة مضادة تتطلب 6 أو 7 ألوان
  3. إطار عمل تقني: تطوير نتائج تقنية أقوى (نسخة معممة من النظرية 1.1 وهي النظرية 1.3)
  4. ابتكار الطريقة: استخدام طريقة التفريغ (discharging method) لتحليل بنية الرسم البياني بشكل منهجي

شرح الطريقة

تعريف المهمة

الإدخال: رسم بياني G قابل للتضمين في الطارة أو زجاجة كلاين، مستوفٍ لشروط طول الدورة، وتخصيص قائمة 5-لونية L الإخراج: تلوين L-مناسب بحيث يظهر لون معين عدداً فردياً من المرات في الحي المجاور لكل رأس غير معزول القيود:

  • بدون دورات بأطوال 3 و4 و6
  • بدون دورتي 5 تشتركان في حافة

الطرق التقنية الأساسية

مفهوم طول R

بالنسبة للرسم البياني G ومجموعة الحواف R ⊆ E(G)، يُعرّف طول R للدورة C بأنه |E(C)| + |E(C) ∩ R|. يوحد هذا المفهوم معالجة المشكلة الأصلية والنسخة المعممة.

الرؤوس المرتاحة R

الرأس v هو مرتاح R إذا:

  • deg(v) فردي أو 0، أو
  • v مجاور لحافة ما في R

النظرية التقنية الرئيسية (النظرية 1.3)

ليكن G قابلاً للتضمين في الطارة أو زجاجة كلاين، R ⊆ E(G). إذا:

  • لا توجد دورات بطول R يساوي 3 أو 4 أو 6
  • لا توجد دورتان بطول R يساوي 5 تشتركان بالضبط في حافة واحدة

فإنه لكل تخصيص قائمة 5-لونية L، يوجد تلوين L-مناسب بحيث يظهر لون معين عدداً فردياً من المرات في الحي المجاور لكل رأس غير مرتاح R.

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

تحليل المثال المضاد الأدنى

بافتراض وجود مثال مضاد أدنى G، يتم تحليل خصائصه البنيوية:

  1. الاتصالية: إثبات أن G يجب أن يكون متصلاً (Lemma 3.1)
  2. الحد الأدنى للدرجة: كل رأس له درجة على الأقل 3 (Lemma 3.2)
  3. قيود الرؤوس ثلاثية: لا يمكن للرؤوس ثلاثية الدرجة أن تكون مجاورة لعدد كبير جداً من الرؤوس المرتاحة R (Lemma 3.3)
  4. بنية الدورات: تحليل مفصل لطول R للدورات ثلاثية والرباعية والخماسية وعلاقاتها المتبادلة

طريقة التفريغ

استخدام تقنية التفريغ الكلاسيكية:

الشحنة الأولية:

  • الرأس v: ch(v) = deg(v) - 4
  • الوجه f: ch(f) = leng(f) - 4

قواعد التفريغ (R1)-(R8):

  • (R1): الوجوه (≥5) ترسل 1/2 وحدة شحنة للرؤوس المجاورة ثلاثية الدرجة
  • (R2)-(R6): معالجة نقل الشحنة بين الوجوه
  • (R7): الرؤوس (≥5) ترسل 1/2 وحدة شحنة للوجوه المجاورة خماسية الأضلاع
  • (R8): الرؤوس (≥6) ترسل 1/3 وحدة شحنة للوجوه الخماسية المستوفية للشروط

تحليل الشحنة

من خلال حسابات شحنة دقيقة، يتم إثبات:

  • الشحنة النهائية لكل رأس ووجه غير سالبة
  • إجمالي الشحنة موجب بشكل صارم
  • هذا يتناقض مع صيغة أويلر، مما ينفي وجود المثال المضاد

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

التحقق النظري

هذه ورقة نظرية بحتة، يتم التحقق من النتائج بشكل أساسي من خلال الإثبات الرياضي:

  1. الإثبات البنائي: لتلوين الرسوم البيانية المستوفية للشروط، يتم إعطاء تلوين فردي 5 بشكل بنائي
  2. بناء الأمثلة المضادة: إثبات أمثلية عدد الألوان 5
    • الدورة الخماسية ليست فردية 4-قابلة للتلوين
    • التقسيم 1 من K7 ليس فردي 6-قابل للتلوين
    • التقسيم 1 من K6 ليس فردي 5-قابل للتلوين

الأدوات التقنية

  • صيغة أويلر للقيود على الرسوم البيانية على السطوح
  • التطبيق المنهجي لطريقة التفريغ
  • تقنيات التحليل المحلي لبنية الرسم البياني

نتائج التجارب

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

النظرية 1.1 (النظرية الرئيسية)

الرسم البياني G القابل للتضمين في الطارة أو زجاجة كلاين والخالي من الدورات بأطوال 3 و4 و6 وبدون دورتي 5 تشتركان في حافة هو فردي 5-قابل للاختيار.

النتيجة الطبيعية 1.2

الرسم البياني G القابل للتضمين في الطارة أو زجاجة كلاين والخالي من الدورات بأطوال 3 و4 و6 و8 هو فردي 5-قابل للاختيار.

الأمثلية

  • عدد الألوان 5 هو الأمثل: الدورة الخماسية تتطلب 5 ألوان
  • قيود طول الدورة ضرورية: توجد أمثلة مضادة بمحيط 6 تتطلب 6-7 ألوان

التحقق من النتائج التقنية

تم إثبات اللمات الرئيسية من خلال تحليل بنيوي مفصل:

  • Lemma 3.5: يجب أن تكون الدورات الثلاثية بطول R يساوي 5، وجميع الرؤوس مرتاحة R
  • Lemma 3.16: لا يمكن للرؤوس رباعية الدرجة أن تكون مجاورة فقط للوجوه رباعية الأضلاع
  • Lemma 4.11: بعد التفريغ، إجمالي الشحنة موجب بشكل صارم

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

تطور أبحاث التلوين الفردي

  1. الأصل: Petruševski و Škrekovski (2022) قدما المفهوم وحدسا أن الرسوم البيانية المستوية هي فردية 5-قابلة للتلوين
  2. نتائج الرسوم البيانية المستوية:
    • الإثبات الأولي: فردي 9-قابل للتلوين
    • التحسين: أثبت Petr و Portier أنها فردية 8-قابلة للتلوين
  3. التعميم على السطوح: أثبت Metrebian وكذلك Tian و Yin أن رسوم البيانية على الطارة هي فردية 9-قابلة للتلوين

خلفية تلوين القوائم

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

مساهمات المنهجية

  • تطبيق طريقة التفريغ في التلوين الفردي
  • إدخال مفهوم طول R يوحد معالجة الحالات المختلفة
  • توفير إطار عمل تقني للأبحاث اللاحقة

الخلاصة والمناقشة

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

  1. تحت قيود البنية الدورية المناسبة، للرسوم البيانية على الطارة وزجاجة كلاين خصائص تلوين قائمة فردية جيدة
  2. 5 ألوان كافية للتعامل مع هذه الفئة من الرسوم البيانية، وهذا الحد محكم
  3. طريقة التفريغ هي أداة فعالة لتحليل هذه الأنواع من المشاكل

القيود

  1. قيود السطح: النتائج تنطبق فقط على السطوح ذات جنس أويلر على الأكثر 2
  2. شروط الدورة: يتطلب استبعاد عدة أنواع من الدورات القصيرة، الشروط معقدة نسبياً
  3. البناء: الإثبات وجودي، لم يقدم خوارزمية فعالة

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

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

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

المميزات

الابتكار التقني

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

المساهمات النظرية

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

القيمة الأكاديمية

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

أوجه القصور

القيود التقنية

  1. شروط صارمة: المتطلبات على بنية الدورات معقدة نسبياً، قد تحد من التطبيقات العملية
  2. قيود السطح: تتعامل فقط مع أبسط الحالات غير البديهية للسطوح
  3. غياب الخوارزمية: لم يتم إعطاء خوارزمية محددة لبناء التلوين الفردي

عمق التحليل

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

التأثير

التأثير النظري

  • توفير أدوات تقنية مهمة ونتائج لتطور نظرية التلوين الفردي
  • قد تلهم اتجاهات بحثية جديدة في نظرية تلوين الرسوم البيانية على السطوح
  • قد يؤثر تطبيق جديد لطريقة التفريغ على تقنيات الإثبات ذات الصلة

القيمة العملية

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

قابلية التكرار

  • الإثبات كامل ومفصل، المسار التقني واضح
  • يمكن التحقق من النتائج الرئيسية بشكل مستقل
  • توفير أساس متين للأعمال اللاحقة

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

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

المراجع

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

النظرية الأساسية:

  • أعمال متعلقة بنظرية الألوان الأربعة 4,5,6,34
  • نظرية تلوين الرسوم البيانية على السطوح 3,18,20,22,33

أبحاث التلوين الفردي:

  • أصل المفهوم 32
  • نتائج الرسوم البيانية المستوية 31,14,11
  • التعميم على السطوح 29,36

الطرق التقنية:

  • تطبيقات طريقة التفريغ 25
  • مشاكل تلوين ذات صلة 1,2,10,12,16,17,24,26,27

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