شاهد لكل لون: لماذا يختلف عن نجاح كل رأس؟

الخلاصة السريعة

في تلوين b نحتاج شاهدًا واحدًا على الأقل لكل لون مستخدم، يرى عند جيرانه جميع الألوان الأخرى. لا يلزم أن ينجح كل رأس. الخماسية والمسار ذو الرؤوس الخمسة يقبلان ثلاثة بهذه القاعدة؛ في التوزيع 1 2 3 1 2 يكون D شاهد اللون 1، وB شاهد 2، وC شاهد 3. المطلوب أكبر عدد يحقق القاعدة، لا أقل عدد عادي.

• التلوين الصحيح يختلف عند طرفي كل حافة. [2] وفي b-coloring تضم كل فئة لون رأسًا مجاورًا لبقية الفئات؛ العدد b-chromatic هو أكبر عدد ألوان يسمح بذلك. [1] نعالج رسمًا محدودًا وبسيطًا وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة؛ لكل رأس لون واحد، والحواف اتصالات فقط.
• نعد الألوان المستخدمة فعلًا والفئات غير الفارغة. لكل لون شاهد واحد على الأقل يرى كل الألوان الأخرى عند جيرانه المباشرين؛ يجوز وجود عدة شهود للون، ورؤوس غير ناجحة في الفئة نفسها. هذا يحقق ظهور كل زوج في الرسم، لكنه أضعف من نجاح كل رأس وأقوى من ظهور الأزواج وحده.
• الخماسية C5 بالتوزيع 1 2 3 1 2 صحيحة وشهودها D وB وC للألوان 1 و 2 و 3. A وE لا يريان 3، فلا يحقق التوزيع شرط كل رأس، ومع ذلك يحقق شهود الفئات. كل شاهد يحتاج إلى k-1 جارًا، فيحد العدد أقصى درجة زائد 1، ومع حد عدد الرؤوس يثبت الأكبر 3 للخماسية.
• في المسار P5 بالحواف AB BC CD DE، التوزيع 1 2 3 1 2 له الشهود D وB وC أيضًا؛ الأكبر 3 رغم الورقتين، بينما شرط كل رأس يسمح 2 فقط. أما P4 بالتوزيع 1 2 3 1 فهو كامل الأزواج لكن لون 1 بلا شاهد. ثلاثة شهود تحتاج ثلاثة رؤوس درجتها 2 على الأقل، ولا يوجد إلا B وC؛ الأكبر 2.
• التلوين الصحيح بأقل عدد يملك شاهدًا لكل فئة: لو غاب شاهد فئة، أمكن إعادة تلوين كل رأس فيها بلون لا يراه عند جيرانه، وحذف الفئة المستقلة دون نزاع، فيتناقض ذلك مع الأقل. إذن الحل موجود هنا دائمًا؛ لكن الأصغر ليس الأكبر، كما يوضح P5 بأقل عادي 2 وأكبر بشهود 3.
• الحافة AB مع معزولين تقبل 2؛ A وB شاهدان، ولا نطلب نجاح المعزولين. الرباعية والنجمة وحافتان منفصلتان أكبرها 2؛ المثلث 3 وK4 أربعة والرؤوس بلا حواف 1. السداسية أكبرها 3 مع 1 2 3 1 2 3، بينما شرط كل رأس يقبل فيها 2 و 3؛ النجمة ترفض أكثر من 2 لغياب شاهد لون الورقة.
• حصرنا كل 64 رسمًا على أربعة رؤوس:960 تقسيمًا، منها 337 صحيحة و 117 تحقق الشهود. اتفق فحص الرؤوس والفئات في 960 حالة، وراجع البحث المستقل الأكبر عبر 8615 تعيينًا مسمى كاملًا. التوزيع 1: واحد،2: أربعون،3: اثنان وعشرون،4: واحد؛ لا فجوة مع الأقل العادي داخل هذا الحصر فقط. C5 وP5 وC6 خارجه.

نبحث عن شاهد في كل فئة، لا في كل رأس

التلوين الصحيح يجعل طرفي كل حافة مختلفين. [2] وفي b-coloring تحتوي كل فئة لون رأسًا مجاورًا لجميع الفئات الأخرى؛ والعدد b-chromatic هو أكبر عدد ألوان يسمح بهذا التلوين. [1]

نستعمل رسمًا محدودًا وبسيطًا وغير موجه، بلا حلقات أو حواف متوازية أو أوزان، ومجموعة رؤوس غير فارغة. كل رأس يأخذ لونًا واحدًا، والحواف تحدد الجيران المباشرين ولا تحمل ألوانًا مستقلة.

فئة اللون هي مجموعة الرؤوس التي تحمل ذلك اللون، وهي مستقلة في التلوين الصحيح: لا توجد حافة بين رأسين فيها. كل فئة مستعملة غير فارغة؛ اسم لون في المفتاح دون رأس لا يكبر العدد.

نسمي رأسًا شاهدًا للونه إذا رأى كل لون آخر مستخدم بين جيرانه. لون الشاهد موجود عليه هو، فلا نطلب جارًا باللون نفسه. رؤية رأس بعيد على بعد خطوتين لا تكفي، ولا تنتقل الرؤية عبر الفراغ بين المكونات.

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

الفحص يختار شاهدًا من كل لون مختلف، فتكون الشهود المختارة رؤوسًا مختلفة. لا يمكن لرأس بلون 1 أن يشهد نيابة عن اللون 2 لمجرد أنه يرى اللون 2؛ لكل لون رأس منه ينفذ طلبه.

في الصور ألوان الدوائر للرؤوس، والخطوط الرمادية حواف الأصل كلها. الأرقام بجانب الخط تسجل زوج ألوان طرفيه، وليست ألوانًا مستقلة للحواف. السطر أسفل الصورة يسمي الشهود المطلوبة صراحة.

الخماسية تنجح بثلاثة رغم فشل رأسين

الخماسية A-B-C-D-E-A لها الحواف AB AE BC CD DE. أعطِ الرؤوس بالترتيب 1 2 3 1 2. طرفا كل حافة مختلفان؛ عند الإغلاق E2 وA1 أيضًا مختلفان، فيكون التلوين صحيحًا.

فئة اللون 1 تضم A وD. الرأس D يجاور C3 وE2، فيرى اللونين الآخرين 2 و 3 ويشهد للون 1. أما A فيجاور B2 وE2 فقط، فلا يرى 3؛ لا يفسد ذلك شهادة D للفئة نفسها.

فئة اللون 2 تضم B وE. الرأس B يجاور A1 وC3، فيرى 1 و 3 ويشهد للون 2. الرأس E يجاور D1 وA1 فيفتقد 3؛ وجود B يكفي لفئة اللون 2.

فئة اللون 3 هي C وحده. جاراه B2 وD1 يظهران اللونين الآخرين 1 و 2، فيشهد للون 3. اكتملت الشهود الثلاثة D وB وC، فالتعيين يحقق القاعدة بثلاثة.

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

لأي لوحة من k ألوان، يحتاج كل شاهد إلى k-1 جارًا على الأقل؛ الجار الواحد لا يحمل لونين. إذن k لا يتجاوز أقصى درجة في الرسم زائد 1، وكذلك لا يتجاوز عدد الرؤوس لأن الفئات غير فارغة.

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

أوراق المسار لا تلزم بأن تكون شهودًا

المسار P5 على A B C D E له AB BC CD DE دون EA. أبقِ التوزيع 1 2 3 1 2. التلوين صحيح؛ D يرى C3 وE2، وB يرى A1 وC3، وC يرى B2 وD1. الشهود D وB وC تحقق الألوان الثلاثة.

A وE ورقتان درجتهما 1، ولا تستطيع أي منهما رؤية لونين آخرين. لكن اللون 1 له D شاهدًا، واللون 2 له B شاهدًا، واللون 3 له C. ليس المطلوب أن تكون كل ورقة شاهدة، ولا أن تتساوى درجات رؤوس الفئة.

أقصى درجة 2، فيمنع الحد أكثر من 3؛ مع شاهد الثلاثة يكون أكبر عدد 3. الأقل العادي 2 بالشاهد 1 2 1 2 1، والحافة تمنع لونًا واحدًا؛ هذه فجوة بين العدد الأقل العادي والأكبر مع شهود.

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

الجدول يراجع ألوان جارَي الشهود الثلاثة في الخماسية والمسار. حذف EA يغير جوار A وE، لكنه لا يغير جوار B أو C أو D المستخدم في الشهادات؛ لذلك تبقى هذه الشهود.

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

ظهور كل زوج لا يصنع شاهدًا لكل لون

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

خذ المسار P4 على A B C D بحواف AB BC CD، ولون الرؤوس 1 2 3 1. الأزواج على الحواف 12 و 23 و 13؛ كل زوج من لوحة الثلاثة موجود، والتلوين صحيح كامل.

لكن فئة اللون 1 هي A وD. A لا يجاور إلا B2، فيفتقد 3؛ وD لا يجاور إلا C3، فيفتقد 2. لا يوجد شاهد للون 1، ولو جمعنا ما يراه A وما يراه D حصلنا على اللونين، لكن الجمع بين رأسين لا يفي بطلب شاهد واحد.

B شاهد اللون 2 لأنه يرى A1 وC3، وC شاهد اللون 3 لأنه يرى B2 وD1. نجاح هذين لا يصلح غياب شاهد اللون 1. الصورة الداخلية اليسرى تعرض الرؤوس والحواف الثلاث كلها دون اختراع حافة AD.

ولا يمكن تلوين P4 آخر بثلاثة أن يحقق القاعدة: يلزم ثلاثة شهود مختلفة، كل منها درجته 2 على الأقل ليرى اللونين الآخرين. لا يوجد في P4 إلا رأسان بهذه الدرجة، B وC. الدرجة القصوى 2 تستبعد أربعة فما فوق.

التناوب 1 2 1 2 صحيح وكل رأس يرى اللون الآخر، فيحقق الشهود بلونين. إذن الأكبر هنا 2، رغم أن التلوين الكامل المعروض يستعمل 3. البرهان يستبعد كل محاولة ثلاثية، وليس الصورة الفاشلة وحدها.

ترتيب الشروط على تعيين بعينه واضح: نجاح كل رأس يضمن شاهدًا لكل فئة، وشهود الفئات تضمن اكتمال الأزواج. المثالان يوضحان فشل العكس: الخماسية بشهود دون نجاح كل رأس، وP4 كامل دون شاهد للون 1.

أما عدم تكرار زوج الألوان في التلوين المتناغم فهو طلب مختلف. القاعدة الحالية لا تمنع تكرار الأزواج؛ في P5 يتكرر 12 على AB وDE، ويظل لكل لون شاهد. لا نستبدل فحص الشاهد بشرط على مرات الزوج.

الأقل العادي يضمن وجود حل، لكنه لا يحدد الأكبر

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

غياب الشاهد يعني أن كل رأس في الفئة يفتقد لونًا آخر بين جيرانه. قد يفتقد رأسان لونين مختلفين؛ لا يلزم وجود لون غائب واحد يصلح للفئة كلها.

أعد تلوين كل رأس في الفئة بأحد الألوان الأخرى التي لا يراها عند جيرانه. لن يتعارض مع جار خارج الفئة لأن اللون المختار غائب عن الجوار الأصلي، وألوان تلك الجيران لا تتغير.

ولا يتعارض رأسان نعيد تلوينهما معًا، لأن الفئة الأصلية مستقلة فلا حافة بينهما. يمكن تنفيذ الاختيارات المتنوعة وحذف اللون الأصلي كله، دون خلق حافة متساوية الطرفين.

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

لهذا يوجد تلوين يحقق شهود الفئات لكل رسم غير فارغ الرؤوس في نموذجنا؛ لا نواجه المجموعة الفارغة التي ظهرت مع شرط كل رأس. مع ذلك، البحث هنا عن الأكبر، وقد يتجاوز الأقل العادي كما حدث في P5.

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

المعزول والنجمة والرباعية تضبط الشهادة

على A B C D مع AB وحدها، لون A1 B2 C1 D1. A يرى اللون 2 عند B فيشهد للون 1، وB يرى 1 عند A فيشهد للون 2. C وD معزولان ولا يريان 2، لكنهما غير مطلوبين كشهود؛ يكفي A للون المشترك معهما.

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

النجمة AB AC AD تقبل A1 B2 C2 D2، فالمركز شاهد 1 وأي ورقة شاهد 2. إذا استعملنا أكثر من 2، حملت الأوراق لونين مختلفين على الأقل؛ ورقة لا ترى إلا لون المركز ولا تستطيع الشهادة للونها أمام لون الورقة الآخر. كل فئة لون أوراق بلا شاهد، فيرفض أكثر من 2 رغم أن حد الدرجة القصوى يسمح 4 نظريًا.

في C4 على AB AD BC CD، التناوب 1 2 1 2 يحقق الشهود. مع ثلاثة ألوان على أربعة رؤوس تتكرر فئة في الرأسين المتقابلين، وتكون الفئتان الأخريان مفردتين ومتقابلتين بلا حافة. الرأس الوحيد في كل منهما لا يرى لون الآخر، فيغيب الشاهد؛ الدرجة 2 تمنع أربعة، فيكون الأكبر 2.

المثلث AB AC BC يقبل A1 B2 C3، وكل رأس شاهد للونه. الدرجة القصوى 2 تمنع أكثر من 3. وفي K4 ذي AB AC AD BC BD CD، أربعة ألوان مختلفة تعطي أربعة شهود، وعدد الرؤوس يمنع الخامس.

السداسية C6 على AB AF BC CD DE EF تقبل 1 2 3 1 2 3؛ كل رأس يرى اللونين الآخرين، فتتحقق الشهود أيضًا. أقصى درجة 2 تمنع أكثر من 3، فيكون الأكبر 3؛ شرط كل رأس له هنا عددان ممكنان 2 و 3.

حافتان منفصلتان AB وCD تقبلان A1 B2 C1 D2، وكل رأس شاهد للونه، والدرجة 1 تحد الأكبر 2. إذا لم توجد أي حافة على الرؤوس الأربعة، فاللون 1 للجميع يحقق الشهادة دون لون آخر مطلوب، والدرجة 0 تحد الأكبر 1.

الجدول يفصل الأقل العادي والأكبر مع شاهد لكل لون ومجموعة الأعداد التي تحقق شرط كل رأس. كلمة «لا يوجد» في عمود كل رأس تعني خلو مجموعة ذلك الشرط، ولا تخص وجود شهود الفئات؛ الأعداد تخص الرسوم المحددة فقط.

الحصر الرباعي لا ينفي فجوة المسار الخماسي

ثبتنا A B C D والأزواج الممكنة AB AC AD BC BD CD، وأخذنا كل قائمة من إبقاء أو حذف الحواف الست. عدد المدخلات 2^6=64، مع بقاء الرؤوس الأربعة حتى حين تنعزل.

لكل مدخل حصرنا 15 تقسيمًا إلى فئات غير فارغة، ووحدنا أسماء الألوان حسب أول ظهور. بلغ المجموع 960 مرشحًا، منها 337 تلوينًا صحيحًا و 117 يملك شاهدًا لكل فئة.

فحصنا لكل رأس ألوان جيرانه، وجمعنا الشهود بحسب لون الرأس. وبطريقة مستقلة، فحصنا لكل فئة وجود رأس منها له جار داخل كل فئة أخرى. اتفق الفحصان في 960 حالة، بما فيها المرفوضة.

أكبر عدد مع الشهود موزع هكذا: رسم واحد عدده 1، وأربعون عددها 2، واثنان وعشرون عددها 3، وواحد عدده 4. مجموع المدخلات 64؛ الأعداد ليست عدد التلوينات المقبولة، الذي بلغ 117 بعد توحيد الأسماء.

لم نجد فرقًا بين الأقل العادي والأكبر مع الشهود في هذه المدخلات الرباعية. هذا لا ينفي الفجوة العامة: P5 بخمسة رؤوس له أقل عادي 2 وأكبر بشهود 3، وقد برهنا المثال خارج هذا الحصر.

راجعنا الأكبر ببحث مستقل في ألوان مسماة؛ نبدأ من الأصغر بين عدد الرؤوس وأقصى درجة زائد 1 ثم ننزل. نشترط استعمال كل اسم، ونوقف البحث عند أول شاهد للعدد ثم أول عدد ناجح. بلغ مجموع التعيينات الكاملة المجربة 8615، واتفق الأكبر مع الحصر في المدخلات 64.

عدد 8615 يحصي تعيينات كاملة جربها البحث، لا عقد بحث جزئية ولا كل الحلول المسماة. أما 960 فتقسيمات توحد الأسماء؛ اختلاف العددين متوقع ولا يدل على سرعة أو ضمان عام.

النماذج الرئيسية والأعداد الرباعية حُفظت قبل البحث في المراجع. أضفنا فحص P4 وبرهانه بوصفه مثالًا أصليًا مساعدًا قبل المسودة، بعد قراءة تعريف المرجع، ولم ننسبه إلى مصدر. C5 وP5 بخمسة رؤوس وC6 بستة خارج الحصر الرباعي، والصور من قوائمنا دون ادعاء ابتكار التعريف أو الأمثلة المعروفة.