ندرس العدد اللوني القوي \(\chi_1(G)\) للرسوم البيانية المستوية \(G\) ونبين أن هناك عائلة لا نهائية من الرسوم البيانية المستوية \(G\) بحيث \(\chi_1(G) = 3\)، وبذلك نحل مشكلة حديثة طرحها Bacsó et al. (The robust chromatic number of graphs, arXiv preprint no. 2305.01923).
في هذه الورقة، ننظر في الرسوم البيانية البسيطة؛ أي الرسوم البيانية بدون حلقات أو حواف متعددة. تعتبر الدالة \(f \, : \, V(G) \rightarrow E(G) \cup \set{\emptyset}\) اختياراً بمعامل واحد للرسم البياني \(G\) إذا كان لكل \(v \in V(G)\) إما أن \(f(v)\) متجاورة مع \(v\) أو \(f(v) = \emptyset\). بعبارة أخرى، \(f\) تعيين بحيث لا يزيد عن حافة واحدة متصلة بكل رأس من رؤوس الرسم البياني. نسمي مجموعة الحواف الناتجة \(f(V(G))\) مجموعة اختيار بمعامل واحد. من الواضح أن كل مكون من الرسم البياني الناتج عن أي مجموعة اختيار بمعامل واحد هو رسم بياني يحتوي على دورة واحدة على الأكثر.
بالنظر إلى اختيار بمعامل واحد \(f\)، يطلق على الرسم البياني \(G_f\) الذي يتم الحصول عليه من \(G\) بحذف الحواف من \(f(V(G))\) الرسم البياني الفرعي المحذوف بمعامل واحد لـ \(G\) بالنسبة لـ \(f\). باستخدام مجموعة جميع الرسوم البيانية الفرعية المحذوفة بمعامل واحد لـ \(G\)، نعرف العدد اللوني القوي لرسم بياني \(G\) كما يلي \[\chi_1(G) = \min_f \chi(G_f)\,,\] حيث \(\chi(G_f)\) هو العدد اللوني لـ \(G_f\).
تم تقديم مفهوم التلوين القوي مؤخراً بواسطة باتكوس، توزا، وفيزر (PatTuzViz23)، الذين استخدموه كأداة لاشتقاق تقديرات على مشكلة توران النمطية القصوى. بعد ذلك، تم إجراء تحقيق منهجي للعدد اللوني القوي والثوابت القوية الأخرى بواسطة باتشو وآخرين في (BacPatTuzViz23)، وفي (BacBujPatTuzViz23)، تم تقديم نتائج لبعض فئات الرسوم البيانية المحددة.
على وجه الخصوص، للعدد اللوني القوي، تم استنتاج النتيجتين العامتين التاليتين.
لأي رسم بياني \(G\)، ينطبق ما يلي \[\bigg\lceil \frac{\chi(G)}{3} \bigg\rceil \le \chi_1(G) \le \chi(G)\,.\] علاوة على ذلك، كلا الحدين محكمان.
[thm:deg] لأي رسم بياني \(d\)-متدهور \(G\)، ينطبق ما يلي \[\chi_1(G) \le \frac{d}{2} + 1\,.\] علاوة على ذلك، هذا الحد الأعلى محكم حيث لكل عدد صحيح \(k \ge 1\) يوجد رسم بياني \(2k\)-متدهور \(H_k\) بحيث \(\chi_1(H_k) = k+1\).
كنتيجة مباشرة للنظرية [thm:deg]، يمكن الحصول على حدود عليا للرسوم البيانية الخارجية، الرسوم البيانية المستوية الخالية من المثلثات، والرسوم البيانية المستوية، حيث، بموجب صيغة أويلر، فهي \(2\)-متدهورة، \(3\)-متدهورة، و\(5\)-متدهورة، على التوالي.
[cor:plan]
لأي رسم بياني خارجي \(G\)، ينطبق ما يلي \(\chi_1(G) \le 2\). (BacPatTuzViz23)
لأي رسم بياني مستوٍ خالٍ من المثلثات \(G\)، ينطبق ما يلي \(\chi_1(G) \le 2\).
لأي رسم بياني مستوٍ \(G\)، ينطبق ما يلي \(\chi_1(G) \le 3\). (BacPatTuzViz23)
كل من الحالتين الأولى والثانية من النتيجة [cor:plan] محكمتان، بينما بالنسبة للحالة \((iii)\)، لم يكن واضحاً ما إذا كان يمكن تحقيق الحد الأعلى بواسطة بعض الرسوم البيانية المستوية، لذلك اقترح باتشو وآخرون (BacPatTuzViz23) هذا السؤال كمشكلة.
هل توجد رسوم بيانية مستوية بحيث \(\chi_1(G) = 3\)، أم أن \(2\) هو الحد الأعلى العام؟
إن صحة الجزء الأخير ستوفر ميزة مثيرة للاهتمام بأن أي رسم بياني مستوٍ يقبل مجموعة اختيار بمعامل واحد يؤدي حذفها إلى الحصول على رسم بياني مستوٍ ثنائي الألوان. ومع ذلك، هذه ليست الحالة كما نوضح في هذه الملاحظة.
[thm:main] هناك عائلة لا نهائية من الرسوم البيانية المستوية \(G\) بحيث \(\chi_1(G) = 3\).
نذكر هنا أنه، كما لاحظ فويغت (Voi24)، يمكن الحصول على النتيجة أعلاه أيضاً من خلال نهج مختلف، باستخدام نتيجة كيمنيتز وفويغت (KemVoi18) حول التلوين بالقائمة للرسوم البيانية المستوية.
تنظم بقية الورقة على النحو التالي. في القسم [sec:prel]، نعرف المفاهيم المستخدمة لاحقاً، في القسم [sec:proof]، نثبت النظرية [thm:main]، وفي القسم [sec:conc]، نختتم ببعض الاتجاهات للعمل المستقبلي.
في هذا القسم، نقدم المفاهيم والمصطلحات التي نستخدمها في براهيننا.
لمجموعة من الحواف \(S\)، نعني بـ \(G - S\) الرسم البياني الذي يتم الحصول عليه بإزالة حواف \(S\) من \(G\)، وبـ \(G[S]\) نعني الرسم البياني الفرعي لـ \(G\) الذي يتم تحريضه بواسطة حواف \(S\).
لـ رسم بياني مستوٍ \(G\)، أي رسم بياني مستوٍ مع تضمين معين في المستوى، مع \(V(G)\)، \(E(G)\)، و \(F(G)\) نعني مجموعته من الرؤوس، الحواف، والوجوه، على التوالي. الحواف التي تحد وجهاً \(f\) في رسم بياني مستوٍ هي حواف الحدود لـ \(f\). في رسم بياني مستوٍ متصل، طول أقصر مسار مغلق على طول الحواف التي تحد وجهاً \(f\) هو طول \(f\)، ويرمز له بـ \(\ell(f)\). إذا لم يكن الرسم البياني متصلاً، فإن طول وجه \(f\) هو مجموع أطوال أقصر المسارات المغلقة التي تحد \(f\). وجه بطول \(k\) يسمى وجه \(k\). في رسم بياني مستوٍ ثنائي الاتصال، حواف الحدود لكل وجه تشكل دورة (MohTho01)، بينما في الرسوم البيانية المستوية غير المتصلة قد تتألف حدود الوجوه من عدة أجزاء (غير متصلة). على وجه الخصوص، إذا احتوى حد وجه على جسر، فإن هذه الحافة تُحسب مرتين في طول الوجه لأن المسار الحدودي يمر بها مرتين. من ناحية أخرى، كما أظهر ويتني (Whi33)، فإن الرسم البياني المستوي ثلاثي الاتصال له تضمين فريد (حتى التكافؤ) في المستوى.
إذا كان كل وجه في رسم بياني مستوٍ \(G\) بطول \(3\)، فإن \(G\) هو تثليث، وبالمثل، \(G\) هو تربيع إذا كان كل وجه فيه بطول \(4\). نذكر أن كل تربيع مستوٍ هو ثنائي الأطراف.
المزدوج (الهندسي) \(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\) من الحواف من \(G\)، نرمز لمجموعة الحواف المقابلة في \(G^*\) بـ \(S^*\). علاوة على ذلك، إذا كان \(G\) تثليثاً، فإن \(G^*\) هو رسم بياني مكعب بلا جسور وبالتالي يحتوي على تطابق مثالي (Pet1891).
قبل أن نقدم الإثبات للنظرية، نذكر عدة نتائج مساعدة. نبدأ بتوضيح الملاحظة من تعريف اختيارات \(1\).
[prop:unicyc] لنفترض أن \(H\) هو رسم بياني فرعي لرسم بياني \(G\) يتم استحداثه بواسطة بعض مجموعات الحواف في \(G\). عندئذ، كل مكون من مكونات \(H\) يحتوي على دورة واحدة على الأكثر إذا وفقط إذا كان \(H\) مجموعة اختيار \(1\).
لنفترض أولاً أن كل مكون من مكونات \(H\) يحتوي على دورة واحدة على الأكثر. إذا لم يحتو \(C\) على دورة، فإننا نختار رأساً عشوائياً من الشجرة \(C\) ليكون \(v_r\)، والذي يمثل جذر الشجرة المعنية. إذا احتوى \(C\) على دورة، فإننا نوجه حوافها بطريقة دائرية، ثم نقوم بطي الدورة مؤقتاً إلى رأس واحد \(v_r\)، جذر الشجرة الناتجة بهذه الطريقة. الآن نوجه جميع حواف \(C\) بعيداً عن \(v_r\).
بعد ذلك، نعرف اختيار \(1\) \(f\) بحيث نعين لكل رأس \(v\) من \(C\) الحافة التي يكون رأسها النهائي هو \(v\). لاحظ أنه في حالة عدم احتواء \(C\) على دورة، فإن الرأس \(v_r\) لا يعين له أي حافة. هذا يثبت الدلالة الصحيحة.
للدلالة العكسية، لنفترض أن \(H\) هو مجموعة اختيار \(1\) ولنفرض عكس ذلك أن هناك مكون \(C\) من \(H\) يحتوي على دورتين على الأقل. في هذه الحالة، \(|E(C)| \ge |V(C)| + 1\)، مما يعني أنه يجب تعيين حافتين على الأقل لنفس الرأس، وهذا تناقض.
نقول إن اختيار \(1\) \(f\) يضمن خاصية \(\mathcal{P}\) لرسم بياني \(G\) إذا كان \(G_f\) يمتلك الخاصية \(\mathcal{P}\)؛ وبالمثل، مجموعة اختيار \(1\) تضمن خاصية \(\mathcal{P}\) لـ \(G\). في البرهانين التاليين، نستخدم مفهوم مجموعة اختيار \(1\) الدنيا، والتي نعني بها مجموعة اختيار \(1\) \(S\) التي تضمن ثنائية الأطراف لرسم بياني ولكن إزالة أي حافة من \(S\) لن تضمن ثنائية الأطراف بعد الآن.
[lem:K2OrClaw] لنفترض أن \(G\) هو تثليث مستوٍ. إذا كان \(S \subseteq E(G)\) هو مجموعة اختيار \(1\) الدنيا التي تضمن ثنائية الأطراف لـ \(G\) (أي أن \(G - S\) ثنائي الأطراف)، فإن كل وجه \(3\) في \(G\) يحتوي بالضبط على حافة واحدة أو ثلاث حواف في \(S\). علاوة على ذلك، هناك حد أقصى لحافتين \(3\) بكل حوافها في \(S\).
ليكن \(n = |V(G)|\). بما أن \(G\) هو تثليث مستوٍ، من صيغة أويلر يتبع أن عدد الوجوه \(3\) في \(G\) هو بالضبط \(2n-4\). إذا كان \(G-S\) ثنائي الأطراف، فإن كل وجه \(3\) يجب أن يحتوي على حافة واحدة على الأقل في \(S\). بما أن كل حافة تحد وجهين، فهذا يعني أننا بحاجة إلى على الأقل \(n-2\) حواف لتغطية كل وجه (لاحظ أن تغطية جميع الوجوه بالضبط \(n-2\) حواف يعني أن المزدوج لـ \(G\) يقبل تطابقاً مثالياً). لذا، \(n-2 \le |S| \le n\).
أفترض الآن أن \(uvw\) هو وجه \(3\) بحافتين بالضبط، قل \(uv\) و \(vw\)، في \(S\). ثم، في أي تلوين \(2\) للرسم البياني (ثنائي الأطراف) \(G - S\)، يتلقى الرأسين \(u\) و \(w\) ألواناً مميزة. لذلك، \(v\) له نفس اللون مثل \(u\) أو \(w\)، قل \(u\)، وبالتالي فإن الحافة \(uv\) لا تحتاج أن تكون في \(S\).
أخيراً، لاحظ أنه إذا كانت جميع حواف وجه \(3\) في \(S\)، فإنها تغطي أربعة وجوه \(3\) بالكامل، وبالتالي يمكن أن يكون لدينا حد أقصى لوجهين \(3\) بكل حوافها في \(S\). علاوة على ذلك، الوجهان \(3\) ليسا متجاورين بموجب الاقتراح [prop:unicyc].
من البرهان [lem:K2OrClaw] يتبع أن الرسم البياني \(G^*[S^*]\) المستحث بواسطة حواف \(S^*\) يتألف فقط من حواف معزولة وعلى الأكثر مخلبين \(K_{1,3}\).
لأغراض الذكر وإثبات البرهان التالي، نشير إلى الرؤوس المعزولة باسم دورات متدهورة.
[lem:3faces] لنفترض أن \(G\) هو تثليث مستوٍ. إذا كان \(S \subseteq E(G)\) هو مجموعة اختيار \(1\) الدنيا التي تضمن ثنائية الأطراف لـ \(G\) (أي أن \(G - S\) ثنائي الأطراف)، فإن كل وجه من الرسم البياني \(G^* - S^*\) له حد يتألف من دورتين (ربما متدهورتين) على الأكثر.
لاحظ أنه، بموجب البرهان [lem:K2OrClaw]، قد تظهر دورة متدهورة على حد وجه مرتين على الأكثر (في حالات \(G^*[S^*]\) التي تحتوي على مكونات متماثلة مع \(K_{1,3}\)).
نذكر أنه بما أن \(G\) هو تثليث، \(G^*\) هو مكعب. علاوة على ذلك، بما أن \(S^*\) يغطي جميع رؤوس \(G^*\) و \(G[S^*]\) له فقط رؤوس من الدرجات \(1\) و \(3\)، فإن الرسم البياني \(G^* - S^*\) له درجة قصوى \(2\) وكل وجه يتألف من دورات.
الآن، لنفترض عكس ذلك أن \(g\) هو وجه من \(G^* - S^*\) حدوده تتألف من ثلاث دورات (ربما متدهورة) على الأقل. ليكن \(\mathcal{C}_g^* = \set{C_1^*,C_2^*,\dots,C_\ell^*}\) هي مجموعة دورات الحدود لـ \(g\). بعد ذلك، ليكن \(R^* \subseteq S^*\) هي مجموعة جميع حواف \(S^*\) المجاورة لمجموعة الوجوه من \(G^*\) المقابلة لوجه \(g\) من \(G^* - S^*\). من الواضح أن المجموعة \(R^*\) ليست فارغة. لاحظ أن المجموعة \(R\) في \(G\) المقابلة للمجموعة \(R^*\) تحث رسماً بيانياً فرعياً متصلاً \(G[R]\) من الرسم البياني \(G[S]\)، والذي يحتوي على دورة واحدة على الأكثر بموجب الاقتراح [prop:unicyc].
الآن، ليكن \(R^*_i \subset R^*\) هي الحواف التي تحتوي على رأس نهائي واحد مجاور للدورة \(C_i^* \in \mathcal{C}_g^*\). لاحظ أن حواف كل \(R^*_i\) تشكل قطوعاً في \(G^*\) وبالتالي فإن المجموعات المقابلة \(R_i\) تشكل رسوماً بيانية فرعية من \(G\) مع دورة واحدة على الأقل في كل من مكوناتها وبالتالي أيضاً في \(G[R]\). لذلك، يمكننا أن نفترض أن كل \(R_i\) يشكل مكوناً متصلاً بدورة واحدة، وإلا لكان لدينا بالفعل دورتان على الأقل في \(G[R]\)، وهذا تناقض.
يبقى أن نظهر أن \(G[R]\) يحتوي على دورتين على الأقل، حيث قد يحدث أن لبعض الأزواج من المجموعات \(R_j^*\) و \(R_k^*\)، لبعض \(j,k\in\set{1,\dots,\ell}\)، أن يكون لدينا \(R_j^* \subseteq R_k^*\) أو \(R_k^* \subseteq R_j^*\)، وبالتالي فإن المجموعتين \(R_j\) و \(R_k\) تساهمان فقط بدورة واحدة. ومع ذلك، لاحظ أنه بما أن كل حافة في \(R_j^* \cap R_k^*\) لها رأس نهائي في \(R_j^*\) والآخر في \(R_k^*\)، فلا يمكن أن تظهر في أي \(R_i^*\) آخر، وبالتالي، هناك دورة إضافية واحدة على الأقل في \(G[R]\)، والتي بموجب الاقتراح [prop:unicyc] تعني أن \(S\) ليست مجموعة اختيار \(1\)، وهذا تناقض.
الآن، نحن مستعدون لتقديم إثبات النظرية [thm:main].
من أجل إثبات النظرية، نقوم ببناء رسم بياني مكعب \(3\)-متصل مستوٍ \(G^*\) الذي يكون مزوجه \(G\) له \(\chi_1(G) = 3\).
في التكوين، نستخدم نسخاً من \(T'\) (انظر التكوين الصحيح). التكوين \(T'\) له الخاصية التي إذا احتوى الرسم البياني \(G\) على \(T'\) كرسم بياني جزئي، فإن كل مسار في \(G\)، الذي يستخدم اثنتين من الحواف \(a\), \(b\), \(c\) ويزور جميع رؤوس \(T'\) يحتوي على الحافة \(a\) (Tut46, Ros90). بعبارة أخرى، كل دورة هاميلتونية في \(T\) (انظر الرسم البياني الأيسر) تحتوي على الحافة \(a\).
في الشكل [fig:Tuttes]، يتم تصوير جميع التطابقات الممكنة في \(T'\) التي تحتوي على الحافة \(a\)، وهذا يعني الادعاء التالي.
[cl:2fac] كل \(2\)-عامل في \(T'\)، لا يحتوي على الحافة \(a\)، يحتوي على دورة واحدة على الأقل لا تستخدم الحافتين \(b\) و \(c\).
الآن، ضع في اعتبارك الرسم البياني \(G^*\) في الشكل [fig:theGraph]. يحتوي على ثلاث قطوع بثلاث حواف \(a\) ونسخ من \(T'\) على كل من الجانبين من كل حافة \(a\). بما أنه في الأكثر يوجد رأسان في \(G^*[S^*]\) لهما درجة \(3\)، هذا يعني أنه في الأقل ست نسخ من \(T'\) المقابلة لقطع الثلاث حواف (قل الوسطى، المصورة بحواف أثقل) لها الخاصية التي لأي مجموعة اختيار \(1\) \(R\) تضمن ثنائية القطبية لـ \(G\) على الأقل حافة واحدة \(a\)، دعها \(a_x\)، في تلك القطوع الثلاثة موجودة في المجموعة المقابلة \(R^*\).
لذلك، بموجب الادعاء [cl:2fac]، فإن النسختين المقابلتين من \(T'\) تحتويان على دورة في حدود بعض وجه من \(G^* - R^*\) وبالتالي، الوجه المجاور لـ \(a_x\) له على الأقل ثلاث دورات حدودية في \(G^* - R^*\). بموجب الليما [lem:3faces]، هذا يعني أن \(G - R\) ليست ثنائية القطب.
من أجل الحصول على عائلة لا نهائية من الرسوم البيانية المستوية ذات العدد اللوني القوي المساوي لـ \(3\)، لاحظ أنه يمكن توسيع \(G^*\) بسهولة أكبر، على سبيل المثال، بنسخ من قطوع الثلاث حواف وبالتالي فإن الثنائيات المقابلة لا تزال غير ثنائية القطب.
من ناحية أخرى، هناك فئة كبيرة من الرسوم البيانية المستوية لها العدد اللوني القوي المساوي لـ \(2\).
[prop:2] لكل تثليث مستوٍ \(G\) الذي يقبل ثنائية \(2\)-عامل بحد أقصى دورتين، لدينا أن \(\chi_1(G) = 2\).
ليكن \(C^*\) \(2\)-عامل في \(G^*\) بحد أقصى دورتين. ثم \(S^* = E(G^*) \setminus E(C^*)\) هو تطابق مثالي في \(G^*\). لاحظ أنه يوجد في الأكثر دورة واحدة في \(S\) تتوافق مع القطع في \(S^*\) الممثلة بالحواف ذات النهايات المجاورة لدورتين من \(C^*\). لذلك، \(S\) هو مجموعة اختيار \(1\) بموجب الاقتراح [prop:unicyc]. علاوة على ذلك، بما أن \(S^*\) هو تطابق مثالي، فإن كل وجه بثلاث حواف في \(G\) له حافة واحدة مجاورة في \(S\) وبالتالي الرسم البياني \(G-S\) هو رباعي الأوجه، وبالتالي ثنائي القطب.
من الواضح، أن جميع الرسوم البيانية الجزئية للتثليث من الاقتراح [prop:2] لها أيضاً العدد اللوني القوي بحد أقصى \(2\).
كل رسم بياني مستوٍ \(G\)، وهو رسم بياني جزئي لتثليث مستوٍ ثنائي يقبل \(2\)-عامل بحد أقصى دورتين، له \(\chi_1(G) \le 2\).
تحقيق الثوابت القوية لا يزال في مراحله الأولى، ولكن تم الحصول على عدد من النتائج المثيرة للاهتمام بالفعل. ومع ذلك، لا يزال هناك الكثير من المشكلات المفتوحة في هذا المجال.
على سبيل المثال، استناداً إلى النتيجة المقدمة في هذه الملاحظة، قد يتساءل المرء عن الحد الأعلى للعدد الكروماتي القوي للرسوم البيانية التي يمكن تضمينها على أسطح ذات جنس أعلى. في حالة التورس، كل رسم بياني يمكن تضمينه عليه هو \(6\)-متدهور، وببعض التحليل الإضافي، باستخدام نتيجة (Tho94) حول التلوين الصحيح للرسوم البيانية التورسية، يمكن استنتاج أن كل رسم بياني تورسي \(G\) لديه \(\chi_1(G) \le 3\).
من ناحية أخرى، بالنسبة لـ \(K_{10}\)، الذي له جنس \(4\) وجنس غير قابل للتوجيه \(7\) (انظر، على سبيل المثال، (MohTho01)), لدينا أن \(\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).