لون واحد بلا تكرار: لماذا لا تكفي ثلاثة جيران باللون نفسه؟

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

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

• في التلوين الصحيح يختلف لون طرفي كل حافة. [2] أما Proper Conflict-Free Coloring فيطلب عند كل رأس غير معزول لونًا يظهر مرة واحدة بين جيرانه؛ عدده اللوني هو أقل عدد ألوان يحقق الصحة وهذا الشرط معًا. [1] نفحص رسمًا محدودًا وبسيطًا وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة.
• الشاهد محلي في الجوار المفتوح، فلا نعد الرأس نفسه. يكفي لون واحد بتكرار 1 عند كل غير معزول، ويجوز أن يختلف من رأس لآخر أو يتكرر خارج جواره. لا نطلب اختلاف جميع الجيران. المعزول معفى لكنه ملون؛ الألوان حرة وتبديل أسمائها لا يغير الحل.
• نجمة AB AC AD بتلوين A1 B2 C2 D2 صحيحة، لكن المركز يرى 2 ثلاث مرات بلا لون وحيد التكرار. اللونان يجبران الأوراق على الاتفاق، فلا يكفيان. A1 B2 C2 D3 يعطي المركز تكراري 2 و 1، والأوراق ترى 1 مرة واحدة، فيكون الأقل 3.
• في نجمة AB AC AD AE AF، التلوين A1 B2 C2 D2 E3 F3 يعطي تكراري 3 و 2؛ ينجح شرط العدد الفردي بفضل 3، وشرط لونين مختلفين في الجوار، لكنه يفشل شرط المرة الواحدة. A1 B2 C2 D2 E2 F3 يصلحها بتكراري 4 و 1، والأقل 3. نجمة الأربع أوراق تقبل 3 بتوزيع 3 و 1، وتفشل بتوزيع 2 و 2.
• التكرار 1 فردي، لذلك كل حل صحيح مع لون وحيد التكرار يحقق شرط التكرار الفردي، والعكس يفشل في نجمة الثلاث أوراق. الدرجة الفردية وحدها لا تكفي هنا. عند الدرجة 1 ينجح الجار الوحيد، وعند الدرجة 2 يجب اختلاف الجارين؛ مع صحة الحواف تصبح القيود قيود المربع إذا كانت أقصى درجة 2. عند الدرجة 3، لونان أو أكثر يفرضان 2 و 1 أو 1 و 1 و 1؛ عند الدرجة 4 يمكن أن يفشل 2 و 2 رغم التنوع.
• الأقل في C4 هو 4، وفي C5 هو 5، وفي C6 و P4 و P5 هو 3، بشواهد 1 2 3 4 و 1 2 3 4 5 و 1 2 3 1 2 3 و 1 2 3 1 و 1 2 3 1 2. المثلث 3 والماسة 3 بالشاهد 1 2 3 3 و K4 أربعة؛ الحافة مع معزولين وحافتان منفصلتان 2، وأربعة رؤوس بلا حواف 1. لون منفرد في جوار لا يلزم أن يكون منفردًا في الرسم كله. نجمة بورقتين تحتاج 3 لأن المركز وجاريه يجب أن تختلف ألوانهم.
• حصرنا 64 رسمًا رباعيًا و 960 تقسيمًا مع تجاهل إعادة أسماء الألوان: 337 صحيحًا، و 252 يحقق شرط المرة الواحدة مقابل 256 للتكرار الفردي. اتفق الأقل مع بحث مستقل جرب 1985 تعيينًا كاملًا. زاد الأقل فوق العادي في 31 رسمًا وفوق الفردي في 4؛ التوزيع: رسم واحد يحتاج 1، وتسعة تحتاج 2، وخمسون تحتاج 3، وأربعة تحتاج 4. أمثلة الخمسة والستة رؤوس خارج هذا الحصر؛ نثبت الأقل بشاهد واستبعاد كل عدد أصغر.

لون وحيد التكرار في جوار كل رأس

في التلوين الصحيح يختلف لون طرفي كل حافة. [2] أما Proper Conflict-Free Coloring فيطلب عند كل رأس غير معزول لونًا يظهر مرة واحدة بين جيرانه؛ عدده اللوني هو أقل عدد ألوان يحقق الصحة وهذا الشرط معًا. [1] نفحص رسمًا محدودًا وبسيطًا وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة.

كل رأس يأخذ لونًا واحدًا. ننظر إلى جيرانه المباشرين ونعد مرات كل لون لديهم. ينجح الرأس غير المعزول إذا وجد لون بتكرار 1 بالضبط؛ لا يكفي 3 أو 5، ولو كان العدد فرديًا. لون غير موجود تكراره 0 ولا يصلح شاهدًا.

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

التفرد هنا محلي: اللون الذي يظهر مرة واحدة بين جيران A يمكن أن يظهر مرات أخرى خارج هذا الجوار. لا نفحص حجم فئة اللون في الرسم كله. كما يجوز أن يتكرر لون آخر داخل الجوار ما دام لون واحد على الأقل يظهر مرة واحدة.

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

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

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

ثلاث أوراق بلون واحد تفشل عند المركز

النجمة على A B C D لها الحواف AB AC AD فقط. لا توجد حافة بين ورقتين. التلوين A1 B2 C2 D2 صحيح لأن كل حافة تصل 1 إلى 2، لكن صحة الحواف ليست وحدها الشرط المطلوب.

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

هذا التلوين يحقق شرط التكرار الفردي: 3 فردي عند المركز، و 1 فردي عند الأوراق. لكنه لا يحقق المرة الواحدة. الصورة الرئيسية تعرض النجمة كاملة وتبين سبب الإخفاق؛ لا نتحدث عن خطأ في لون طرفي حافة.

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

غيّر D إلى اللون 3: يصبح الشاهد A1 B2 C2 D3. عند A يظهر 2 مرتين و 3 مرة واحدة، فيشهد اللون 3. كل ورقة ما زالت ترى 1 مرة واحدة، وكل الحواف صحيحة؛ تحقق الشرط عند الرؤوس الأربعة.

استعملنا ثلاثة ألوان، واستبعدنا الواحد بسبب الحافة والاثنين بسبب تكرار لون الأوراق المفروض. ثبت الأقل 3. لا نطلب اختلاف الأوراق كلها: B و C يتفقان، واللون 2 بتكرار 2 لا يفسد نجاح اللون 3 بتكرار 1.

لونان في الجوار قد يتكرران بلا شاهد فريد

خذ نجمة A B C D E F بالحواف AB AC AD AE AF. اختر A1 B2 C2 D2 E3 F3. الخطوط كلها صحيحة؛ يختلف لون المركز عن كل ورقة، ولا توجد حواف بين الأوراق.

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

وجود لونين مختلفين في جوار A لم يكفِ: كلاهما مكرر. كذلك وجود عدد فردي 3 لم يكفِ، مع أنه يحقق شرط التكرار الفردي. هذا المثال يفصل بين تنوع ألوان الجيران ووجود لون وحيد التكرار بينهم.

أعطِ A1 B2 C2 D2 E2 F3 بدلًا من ذلك. عند A يظهر 2 أربع مرات و 3 مرة واحدة، فيشهد اللون 3. كل ورقة ترى 1 مرة واحدة، والتلوين صحيح، فينجح الجميع بثلاثة ألوان.

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

في نجمة الأربع أوراق AB AC AD AE، ينجح A1 B2 C2 D2 E3 بتكراري 3 و 1 عند المركز، ويثبت الأقل 3 بالحجة نفسها ضد اللونين. أما A1 B2 C2 D3 E3 فيعطي 2 و 2، فلا يظهر لون مرة واحدة رغم وجود لونين مختلفين في الجوار.

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

المرة الواحدة أقوى من التكرار الفردي

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

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

في شرط الفردية، الدرجة الفردية الموجبة تضمن وجود تكرار فردي لأن مجموع التكرارات فردي. هنا يمكن أن يكون المجموع 3 أو 5 ناتجًا عن لون واحد مكرر، أو 5 ناتجًا عن 3 و 2، من دون أي 1. لذا لا نستعير كفاية الدرجة الفردية.

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

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

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

المسارات والدورات ذات الدرجة اثنين

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

C4 على A B C D له AB AD BC CD. الجوار يضيف اختلاف AC وBD، فتلزم ألوان مختلفة لكل الأزواج الستة. الشاهد 1 2 3 4 صحيح وله لونان بتكرار 1 عند كل رأس؛ الأقل 4.

C5 بحواف AB AE BC CD DE يضيف من الجوار AC AD BD BE CE. مع الحواف الخمس تغطي القيود جميع أزواج الرؤوس الخمسة، فيلزم 5، ويصلح 1 2 3 4 5. صغر الدرجة لا يسمح بتجاهل هذه الأزواج.

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

P4 بحواف AB BC CD يقبل 1 2 3 1، و P5 بحواف AB BC CD DE يقبل 1 2 3 1 2. الأطراف ترى جارًا واحدًا، والرؤوس الداخلية ترى جارين مختلفين. أي رأس داخلي وجاراه يجبر ثلاثة ألوان مع صحة حافتين، فيثبت الأقل 3.

نجمة بورقتين AB AC تحتاج 3 أيضًا: B و C يجب أن يختلفا عند A، ومع صحة الحافتين يختلف A عنهما. لا نمد قاعدة المربع إلى كل درجة؛ نجمة الخمس أوراق نجحت بتكرار 4 و 1، مع اتفاق كثير من الجيران.

C5 و C6 و P5 والنجمة ذات خمسة أو ستة رؤوس أمثلة مستقلة خارج الحصر الرباعي اللاحق. C4 و P4 داخل حد الأربعة، ونجمة الورقتين على ثلاثة رؤوس أصغر؛ نعلن حواف كل مثال وشاهدًا وسبب استبعاد العدد الأصغر.

لون الشاهد قد يتكرر خارج الجوار

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

الماسة على A B C D لها AB AC AD BC BD، ولا توجد CD. الشاهد A1 B2 C3 D3 صحيح. عند A يظهر 2 مرة واحدة و 3 مرتين، فيشهد اللون 2؛ عند B يظهر 1 مرة واحدة و 3 مرتين، فيشهد اللون 1.

كل من C و D يرى A1 وB2، فيظهر كل لون مرة واحدة في جواره. تحقق الشرط بثلاثة ألوان، والمثلث ABC يمنع أقل منها، فيكون الأقل 3. تكرار 3 عند المركزين مسموح لوجود شاهد آخر.

في الماسة، اللون 1 يشهد لكل من C و D مع أنه رأس واحد يشترك في جواريهما. لا نحتاج رأس شاهد خاصًا لكل رأس، ولا نحذف الجار بعد استعماله شاهدًا. الفحص مستقل لكل جوار.

لتوضح الفرق عن التفرد العالمي، أضف إلى حافة AB معزولين C و D واختر A1 B2 C1 D2. عند A يظهر 2 مرة واحدة لأن جاره B فقط، رغم وجود 2 أيضًا عند D خارج جواره. وعند B يظهر 1 مرة واحدة رغم وجود 1 عند C.

المعزولان ملونان ومعفيان من شرط الجوار. الأقل 2 بسبب الحافة، لا 4 لإعطاء المعزولين لونين جديدين. كذلك حافتان منفصلتان AB وCD تقبلان A1 B2 C1 D2؛ كل رأس يرى جارًا واحدًا.

في K4 ذي AB AC AD BC BD CD، صحة الحواف تفرض 4، وكل رأس يرى ثلاثة جيران مختلفي الألوان بتكرار 1. على أربعة رؤوس بلا حواف، يجوز 1 للجميع مع الإعفاء، فيكون الأقل 1 لا 0.

راجعنا الشاهد الوحيد والأقل بطريقتين

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

قبل فحص الجوار، نجح 337 تقسيمًا في شرط صحة الحواف. عدّينا ألوان كل جوار واشترطنا وجود تكرار 1 عند كل غير معزول، فقبلنا 252. للمقارنة، شرط التكرار الفردي نجح في 256؛ هذه أعداد تقسيمات، لا أعداد الرسوم أو حلول الأقل فقط.

بحث مستقل راجع الأقل بزيادة عدد الألوان وتجربة تعيينات مسماة كاملة. بدل جدول التكرارات، بحث لكل رأس غير معزول عن جار يختلف لونه عن ألوان جميع جيرانه الآخرين؛ هذا الجار يثبت التكرار 1 مباشرة.

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

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

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

للمراجعة العملية، ابدأ بصحة كل حافة، ثم اكتب جيران كل رأس وتكرارات ألوانهم. علّم لونًا بتكرار 1 لكل غير معزول، وسجل إعفاء المعزول. لإثبات الأقل قدم شاهدًا واستبعد كل عدد أصغر؛ وجود لونين في الجوار أو كون الدرجة فردية لا يغني عن العد.