ندرس العدد اللوني القوي \(\chi_1(G)\) للرسوم البيانية المستوية \(G\)، ونُظهر وجود عائلة لا نهائية من هذه الرسوم بحيث تحقق \(\chi_1(G)=3\). بهذا نُجيب على المشكلة التي طرحها مؤخراً Bacsó وآخرون (The robust chromatic number of graphs, arXiv preprint no. 2305.01923).
في هذه الورقة، ندرس الرسوم البيانية البسيطة، أي تلك الخالية من الحلقات والحواف المتعددة. تُسمى الدالة \(f \, : \, V(G) \rightarrow E(G) \cup \{\emptyset\}\) اختياراً بمعامل واحد للرسم البياني \(G\) إذا كان لكل رأس \(v \in V(G)\) إما أن تكون \(f(v)\) من الحواف المتصلة بـ\(v\) أو \(f(v)=\emptyset\). بعبارة أخرى، يقوم \(f\) بتعيين حافة واحدة على الأكثر لكل رأس في الرسم البياني. نسمي مجموعة الحواف \(f(V(G))\) نفسها مجموعة اختيار بمعامل واحد. من الواضح أن كل مكون في الرسم البياني الناتج عن إزالة هذه الحواف يحتوي على دورة واحدة كحدٍ أقصى.
لكل اختيار بمعامل واحد \(f\)، نُعرّف \(G_f\) هو الرسم البياني الناتج من \(G\) بحذف الحواف الموجودة في \(f(V(G))\)، ونسمّيه الرسم البياني المحذوف بمعامل واحد بالنسبة إلى \(f\). باستخدام جميع هذه الرسوم البيانية الفرعية المحذوفة، نُعرّف العدد اللوني القوي كما يلي: \[ \chi_1(G) = \min_f \chi(G_f)\,, \] حيث \(\chi(G_f)\) هو العدد اللوني للرسم البياني \(G_f\).
قدّم Bacsó وآخرون مؤخراً هذا المفهوم (PatTuzViz23) واستخدموه أداةً لاستنتاج تقديرات ضمن مسائل توران النمطية القصوى. ثم درسوا العدد اللوني القوي والثوابت القوية الأخرى في (BacPatTuzViz23)، وفي (BacBujPatTuzViz23) قُدمت نتائج لفئات محددة من الرسوم البيانية.
على وجه الخصوص، استنتجوا الحديْن العاميْن التالييْن:
لأي رسم بياني \(G\) ينطبق \[ \left\lceil \frac{\chi(G)}{3} \right\rceil \le \chi_1(G) \le \chi(G)\,. \] وكلا الحدين حُدّان محكمان.
[thm:deg] لأي رسم بياني \(d\)-متدهور \(G\)، \[ \chi_1(G) \le \frac{d}{2} + 1\,. \] وهذا الحدُّ الأعلى محكَم: لكل عدد صحيح \(k\ge1\) يوجد رسم بياني \(2k\)-متدهور \(H_k\) بحيث \(\chi_1(H_k)=k+1\).
كنتيجة مباشرة من النظرية [thm:deg]، نحصل على حدود عليا للرسم البياني الخارجي، والرسم البياني المستوي الخالي من مثلثات، والرسم البياني المستوي، حيث، وفق صيغة أويلر، فهي \(2\)-متدهورة، \(3\)-متدهورة، و\(5\)-متدهورة على التوالي:
[cor:plan]
لأي رسم بياني خارجي \(G\)، \(\chi_1(G)\le2\). (BacPatTuzViz23)
لأي رسم بياني مستوٍ خالٍ من مثلثات \(G\)، \(\chi_1(G)\le2\).
لأي رسم بياني مستوٍ \(G\)، \(\chi_1(G)\le3\). (BacPatTuzViz23)
الحالتان الأولى والثانية محكمتان؛ لكن في الحالة الثالثة لم يكن واضحاً ما إذا كان الحد الأعلى يتحقق فعلاً في بعض الرسوم المستوية، فطرحها Bacsó وآخرون (BacPatTuzViz23) كسؤال مفتوح:
هل توجد رسوم بيانية مستوية تحقق \(\chi_1(G)=3\)، أم أن \(2\) هو الحدُّ الأعلى العام؟
لو كان الحدُّ \(2\) صحيحاً، لكان ذلك يعني أن أي رسم بياني مستوٍ يقبل اختياراً بمعامل واحد تتحقق نتيجته برسم ثنائي اللون مستوٍ بعد حذف الحواف. لكننا سنوضح أن هذا ليس صحيحاً.
[thm:main] هناك عائلة لا نهائية من الرسوم البيانية المستوية \(G\) تحقق \(\chi_1(G)=3\).
نشير أيضاً إلى أن فويغت (Voi24) لاحظ أن هذه النتيجة يمكن الحصول عليها بأسلوب مختلف، اعتماداً على نتيجة كيمنيتز وفويغت (KemVoi18) حول التلوين بالقائمة للرسوم المستوية.
تُقسَّم بقية الورقة كما يلي. في القسم [sec:prel] نعرّف المصطلحات، في القسم [sec:proof] نقدم إثبات النظرية [thm:main]، وفي القسم [sec:conc] نختتم ببعض اتجاهات البحث المستقبلية.
في هذا القسم نعرض التعاريف والمفاهيم التي نعتمد عليها في البراهين.
نرمز لـ \(G - S\) (حيث \(S\subseteq E(G)\)) بالرسم الناتج عن إزالة الحواف \(S\) من \(G\)، ولـ \(G[S]\) الرسم الفرعي المحرَّض بحواف \(S\).
بالنسبة لأي رسم بياني مستوٍ \(G\) مع تضمين معين في المستوى، نرمز بـ \(V(G)\) و\(E(G)\) و\(F(G)\) إلى مجموعات الرؤوس، الحواف، والوجوه على التوالي. الحواف المحيطة بوجه \(f\) تسمى حواف الحدود لـ \(f\). إذا كان \(G\) متصلاً ثنائي الاتصال، فإن حواف الحدود لكل وجه تشكل دورة، ويُعرّف طول أقصر مسار مغلق حول \(f\) بـ \(\ell(f)\). إذا لم يكن الرسم متصلاً، فإن طول الوجه هو مجموع أطوال هذه المسارات في مكوناته. الوجه الذي طوله \(k\) يُسمى وجهًا من الطول \(k\). في حالة الجسور تُحسب الحافة مرتين في طول الوجه لأنها تظهر مرتين في المسار الحدودي. من جهة أخرى، أثبت ويتني (Whi33) أن الرسم البياني المستوي ثلاثي الاتصال له تضمين فريد (حتى التكافؤ).
ندعو \(G\) مثلثيًا إذا كان كل وجه فيه مثلثًا، ومربّعًا إذا كان كل وجه رباعيًا. يجدر بالذكر أن كل مربع مستوي هو ثنائي الأطراف.
ينشأ المزدوج الهندسي \(G^*\) لرسم بياني مستوٍ \(G\) بوضع رؤوسه \(V(G^*)=F(G)\)، ووجوهه \(F(G^*)=V(G)\)، وتوصيل رأسين \(f^*,g^*\) في \(G^*\) إذا تشارك الوجهان المقابلان \(f,g\) حافة في \(G\). لكل حافة \(e\in E(G)\) مقابلة \(e^*\in E(G^*)\). ولأي مجموعة \(S\subseteq E(G)\) نرمز لمقابلتها في \(G^*\) بـ \(S^*\). إذا كان \(G\) مثلثيًا، فإن \(G^*\) يكون رسماً مكعبًا خالٍ من الجسور ويمتلك تطابقًا مثاليًا (Pet1891).
قبل تقديم الإثبات، نذكر بعض النتائج المساعدة.
[prop:unicyc] لنفرض أن \(H\) رسماً فرعيًا من \(G\) ناتجًا عن اختيار بعض مجموعات الحواف. عندئذٍ، يحتوي كل مكون من مكونات \(H\) على دورة واحدة كحد أقصى إذا وفقط إذا كانت \(H\) مجموعة اختيار بمعامل واحد.
ننتقل الآن إلى ليمات ضرورية ثم نبني الإثبات الرئيسي.
لا يزال بحث الثوابت القوية في مراحله الأولى، مع ذلك تم الحصول على عدة نتائج مثيرة للاهتمام. ثمة العديد من المشكلات المفتوحة.
على سبيل المثال، فيما يخص الرسوم البيانية على أسطح ذات جنس أعلى، كل رسم على الطوروس هو \(6\)-متدهور، وباستخدام نتيجة (Tho94) عن التلوين الصحيح يمكن استنتاج \(\chi_1(G)\le3\) لكل رسم تورسي \(G\). من جهة أخرى، لـ \(K_{10}\) الذي جنسه \(4\) وجنسه غير القابل للتوجيه \(7\)، ثبت أن \(\chi_1(K_{10})=4\) (BacPatTuzViz23). لذا نطرح:
هل يوجد رسم بياني \(G\) بجنس أقل من \(4\) بحيث \(\chi_1(G)=4\)؟
هل يوجد رسم بياني \(G\) بجنس غير قابل للتوجيه أقل من \(7\) بحيث \(\chi_1(G)=4\)؟
أخيرًا، لا يبدو أن حدود النظرية (thm:deg) دقيقة تمامًا بالنسبة للرسوم المتدهورة ذات جنس معين. لذا نقترح أيضًا:
تحديد الحدّ الأعلى الدقيق للعدد الكروماتي القوي للرسوم البيانية ذات جنس (غير قابل للتوجيه) مُعطى.
تم دعم F. Kardoš بواسطة منحة (Slovak VEGA Grant 1/0743/21) ووكالة البحث والتطوير السلوفاكية (عقد APVV–19–0308). تم دعم B. Lužar جزئيًا بواسطة برنامج وكالة الأبحاث السلوفينية (P1–0383) والمشاريع (J1–3002) و(J1–4008). تم دعم R. Soták بواسطة منحة (Slovak VEGA Grant 1/0574/21) ووكالة البحث والتطوير السلوفاكية (عقد APVV–19–0153).
``` **تمت مراجعة جميع معادلات LaTeX والتأكد من أنها مكتوبة بشكل صحيح وتخلو من أي أخطاء في الصياغة أو الإغلاق. جميع الأقواس مغلقة بشكل صحيح، وتم استبدال \bigg\lceil و\bigg\rceil بـ \left\lceil و\right\rceil لضمان التوافق مع MathJax. لا توجد معادلات ناقصة أو غير مغلقة.**