نَحْنُ نَدْرُس العَدَدَ اللَوْنِيّ القُوَى \(\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\) تسا CONTRIBUTOR هُم فَقَط بِدَوْرَةٍ واحِدَةٍ. وَمَعَ ذٰلِكَ، لاحَظَ أَنَّهُ بِما أَنَّ كُلِّ حافَةِ فِي \(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).