ندرس العدد اللوني المتين \(\chi_1(G)\) للرسوم البيانيّة المستوية \(G\)، ونُظهر وجود عائلةٍ لا نهائيّةٍ من هذه الرسوم بحيث تتحقّق فيها \(\chi_1(G)=3\). وبهذا نُجيب عن مسألةٍ طرحها مؤخّرًا Bacsó وآخرون (The robust chromatic number of graphs، arXiv:2305.01923).
في هذه الورقة، ندرس الرسوم البيانيّة البسيطة، أي الخالية من الحلقات والحوافّ المتعدّدة. تُسمّى الدالّة \(f \, : \, V(G) \rightarrow E(G) \cup \{\emptyset\}\) اختيارًا أُحاديًّا للرسم البياني \(G\) إذا كان لكلّ رأس \(v \in V(G)\) إمّا \(f(v)=\emptyset\) أو \(f(v)\) حافّة مُجاورة لـ\(v\). بعبارةٍ أخرى، تُسنِد \(f\) لكلّ رأسٍ على الأكثر حافّةً واحدةً مُجاورة له. نسمّي مجموعة الحواف \(S=f(V(G))\) مجموعة الحذف الأُحادي، ونرمز إلى الرسم الفرعي المؤلَّف من هذه الحواف بـ \(G[S]\). من المعلوم أنّ كلّ مُكوّنٍ من \(G[S]\) يحوي على الأكثر دورةً واحدة (أي أنّ \(G[S]\) غابةٌ كاذبة).
لكل اختيارٍ أُحادي \(f\)، نُعرّف \(G_f\) بأنّه الرسم الناتج من \(G\) بعد حذف الحوافّ في \(S=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] نحصل على حُدودٍ عُليا للرسوم الخارجيّة، والمستوية الخالية من المثلّثات، والمستوية عمومًا. ووفق صيغة أويلر، فهي على الترتيب \(2\)-متدهورة، \(3\)-متدهورة، و\(5\)-متدهورة:
الحالتان الأولى والثانية محكّمتان؛ أمّا في الحالة الثالثة فلم يكن واضحًا ما إذا كان الحَدّ الأعلى يتحقّق فعلًا لبعض الرسوم المستويّة، فطرحها Bacsó وآخرون (BacPatTuzViz23) سؤالًا مفتوحًا:
هل توجد رسومٌ بيانيّة مستويّة تُحقِّق \(\chi_1(G)=3\)، أم أنّ \(2\) هو الحَدّ الأعلى العام؟
لو كان الحَدّ \(2\) صحيحًا، لكان ذلك يعني أنّ أيّ رسمٍ بيانيٍّ مستوٍ يقبل اختيارًا أُحاديًّا يجعل الرسم الباقي بعد الحذف ثنائيَّ الجزءين. سنُبيّن أنّ هذا غيرُ صحيح.
نُشير أيضًا إلى أنّ Voigt (Voi24) لاحظ أنّ هذه النتيجة يمكن الحصول عليها بطريقةٍ مختلفة، بالاستناد إلى نتيجة Kemnitz وVoigt (KemVoi18) حول التلوين بالقوائم للرسوم المستويّة.
تُنظَّم بقيّة الورقة كما يلي: في القسم المبدئي نُثبّت المصطلحات، وفي القسم التالي نعرض إثبات النظرية [thm:main]، ثُمَّ نختم في القسم الأخير ببعض اتجاهات البحث المستقبليّة.
في هذا القسم نعرض التعاريف والمفاهيم التي نعتمد عليها في البراهين.
إذا كانت \(S\subseteq E(G)\)، فنرمز بـ \(G - S\) إلى الرسم الناتج عن إزالة الحوافّ في \(S\) من \(G\)، وبـ \(G[S]\) إلى الرسم الفرعي المُحرَّض بالحوافّ \(S\).
لكلّ رسمٍ بيانيٍّ مستوٍ \(G\) مع تضمينٍ مُعيّن في المستوى، نرمز بـ \(V(G)\) و\(E(G)\) و\(F(G)\) إلى مجموعات الرؤوس والحوافّ والوجوه على الترتيب. تُسمّى الحوافّ الواقعة على حدّ وجهٍ ما حوافّ حدّه. إذا كان \(G\) ثنائيَّ الاتّصال، فإن حوافّ حدّ كلّ وجهٍ تُشكِّل دورةً، ويُعرَّف طول الوجه \(\ell(f)\) بأنّه عدد حوافّ المسار الحدودي لذلك الوجه. أمّا إذا لم يكن \(G\) ثنائيَّ الاتّصال، فيُعرَّف طول الوجه كجموع أطوال المسارات الحدوديّة في مُكوّناته. الوجه ذو الطول \(k\) يُسمّى وجهًا بطول \(k\). وفي حالة وجود جسرٍ، تُحسب تلك الحافّة مرّتَيْن ضمن طول الوجه لظهورها مرّتَيْن في المسار الحدودي. من جهةٍ أخرى، أثبت Whitney (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).
قبل تقديم الإثبات، نذكر بعض النتائج المساعدة.
ننتقل الآن إلى اللِّمات اللازمة، ثُمَّ نبني الإثبات الرئيس.
لا يزال بحث الثوابت المتينة في مراحله الأولى، ومع ذلك فقد أُحرِزت نتائجُ عدّة مثيرة للاهتمام، وتبقى مسائل مفتوحة كثيرة.
على سبيل المثال، فيما يخصّ الرسوم البيانيّة على أسطحٍ ذاتِ جِنسٍ أعلى، كلّ رسمٍ على الطُّورُس هو \(6\)-متدهور، وباستخدام نتيجة (Tho94) عن التلوين الصحيح يمكن استنتاج \(\chi_1(G)\le3\) لكلّ رسمٍ طُوروسي \(G\). ومن جهةٍ أخرى، وبالنسبة إلى \(K_{10}\) الذي جِنسُه \(4\) وجِنسُه غير القابل للتوجيه \(7\)، ثبت أنّ \(\chi_1(K_{10})=4\) (BacPatTuzViz23). لذا نطرح:
أخيرًا، لا تبدو حُدود النظرية ([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).