تخمين هادويجر (نظرية الرسم البياني)

في نظرية الرسم البياني ، تنص تخمينة هادويجر على أنه إذا كانت خالية من الحلقات وليس لها قاصر ، فإن عددها اللوني يفي بـ . ومن المعروف أنها صحيحة بالنسبة إلى . التخمين هو تعميم لنظرية الألوان الأربعة ويعتبر أحد أهم المشاكل المفتوحة وأكثرها تحديًا في هذا المجال. ${\displaystyle G}$${\displaystyle K_{t}}$ ${\displaystyle \chi(G)<t}$${\displaystyle 1\leq t\leq 6}$

بمزيد من التفصيل، إذا استخدمت جميع الألوان المناسبة للرسم البياني غير الموجه لونًا أو أكثر، فيمكن للمرء أن يجد رسومًا بيانية فرعية متصلة منفصلة بحيث يكون كل رسم بياني فرعي متصلًا بحافة بكل رسم بياني فرعي آخر. يؤدي تقليص الحواف داخل كل من هذه الرسوم البيانية الفرعية بحيث ينهار كل رسم بياني فرعي إلى رأس واحد إلى إنتاج رسم بياني كامل على الرؤوس كصغرى لـ .${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$${\displaystyle k}$ ${\displaystyle G}$

تم التوصل إلى هذا التخمين، وهو تعميم واسع النطاق لمشكلة الألوان الأربعة ، بواسطة هوجو هادويجر في عام 1943 وما زال دون حل. ^[1] يطلق عليه بولوباس وكاتلين وإردوش (1980) "واحدة من أعمق المشاكل التي لم يتم حلها في نظرية الرسم البياني". ^[2]

الشكل المكافئ لتخمين هادويجر ( المعاكس للشكل المذكور أعلاه) هو أنه إذا لم يكن هناك تسلسل من تقلصات الحافة (كل منها يدمج نقطتي النهاية لبعض الحواف في قمة عظمى واحدة) التي تجلب الرسم البياني إلى الرسم البياني الكامل ، فيجب أن يكون هناك رأس ملون بالألوان . ${\displaystyle G}$${\displaystyle K_{k}}$${\displaystyle G}$${\displaystyle k-1}$

في التلوين الأدنى لأي رسم بياني ، سيؤدي انكماش كل فئة لون من التلوين إلى رأس واحد إلى إنتاج رسم بياني كامل . ومع ذلك، لا تنتج عملية الانكماش هذه صغرى لأنه لا يوجد (حسب التعريف) أي حافة بين أي رأسين في نفس فئة اللون، وبالتالي فإن الانكماش ليس انكماش حافة (وهو مطلوب للصغرى). تنص تخمينات هادويجر على وجود طريقة مختلفة لانكماش حواف مجموعات الرؤوس بشكل صحيح إلى رؤوس مفردة، مما ينتج رسمًا بيانيًا كاملاً ، بطريقة تكون فيها جميع المجموعات المتقلصة متصلة. ${\displaystyle k}$${\displaystyle G}$${\displaystyle K_{k}}$${\displaystyle G}$${\displaystyle K_{k}}$

إذا كان يشير إلى عائلة الرسوم البيانية التي تتمتع بخاصية أن جميع الرسوم البيانية الثانوية في يمكن تلوينها باللون -، فإنه يتبع من نظرية روبرتسون-سيمور أنه يمكن وصفها بمجموعة محدودة من الثانوية المحظورة . تخمين هادويجر هو أن هذه المجموعة تتكون من ثانوية محظورة واحدة، .${\displaystyle {\mathcal {F}}_{k}}$${\displaystyle {\mathcal {F}}_{k}}$${\displaystyle (k-1)}$${\displaystyle {\mathcal {F}}_{k}}$${\displaystyle K_{k}}$

رقم هادويجر للرسم البياني هو حجم أكبر رسم بياني كامل يكون أصغر من (أو يمكن الحصول عليه بشكل مكافئ عن طريق انكماش حواف ). يُعرف أيضًا باسم رقم الزمرة الانكماشية لـ . ^[2] يمكن صياغة تخمين هادويجر في الشكل الجبري البسيط حيث يشير إلى العدد اللوني لـ .${\displaystyle h(G)}$${\displaystyle G}$${\displaystyle k}$${\displaystyle K_{k}}$${\displaystyle G}$${\displaystyle G}$ ${\displaystyle G}$${\displaystyle \chi (G)\leq h(G)}$${\displaystyle \chi (G)}$ ${\displaystyle G}$

الحالة تافهة: يتطلب الرسم البياني أكثر من لون واحد إذا وفقط إذا كان له حافة، وكانت تلك الحافة نفسها ثانوية . الحالة سهلة أيضًا: الرسوم البيانية التي تتطلب ثلاثة ألوان هي الرسوم البيانية غير ثنائية الأجزاء ، وكل رسم بياني غير ثنائي الأجزاء له دورة فردية ، والتي يمكن تقليصها إلى دورة ثلاثية، أي ثانوية. ${\displaystyle k=2}$${\displaystyle K_{2}}$${\displaystyle k=3}$${\displaystyle K_{3}}$

في نفس الورقة التي قدم فيها التخمين، أثبت هادويجر صحته لـ .${\displaystyle k=4}$ الرسوم البيانية التي لا تحتوي على قاصر هي الرسوم البيانية المتسلسلة المتوازية والرسوم البيانية الفرعية الخاصة بها. يحتوي كل رسم بياني من هذا النوع على رأس به حافتان واردتان على الأكثر؛ يمكن للمرء تلوين أي رسم بياني من هذا القبيل بثلاثة ألوان عن طريق إزالة رأس واحد، وتلوين الرسم البياني المتبقي بشكل متكرر، ثم إضافة الرأس المحذوف وتلوينه مرة أخرى. نظرًا لأن الرأس المحذوف يحتوي على حافتين على الأكثر، فسيكون أحد الألوان الثلاثة متاحًا دائمًا لتلوينه عند إضافة الرأس مرة أخرى. ${\displaystyle K_{4}}$

حقيقة التخمين لـ تعني نظرية الألوان الأربعة : لأنه إذا كان التخمين صحيحًا، فإن كل رسم بياني يتطلب خمسة ألوان أو أكثر سيكون له لون ثانوي وسيكون (بموجب نظرية فاغنر ) غير مستوٍ. أثبت كلاوس فاغنر في عام 1937 أن الحالة تعادل في الواقع نظرية الألوان الأربعة وبالتالي نعلم الآن أنها صحيحة. كما أظهر فاغنر، يمكن تحليل كل رسم بياني ليس له لون ثانوي من خلال مجموعات الزمر إلى قطع إما مستوية أو سلم موبيوس ذي 8 رؤوس ، ويمكن أن تكون كل قطعة من هذه القطع رباعية الألوان بشكل مستقل عن بعضها البعض، وبالتالي فإن قابلية التلوين الرباعية للرسم البياني الخالي من الألوان الثانوية تتبع من قابلية التلوين الرباعية لكل قطعة مستوية. ${\displaystyle k=5}$${\displaystyle K_{5}}$${\displaystyle k=5}$${\displaystyle K_{5}}$${\displaystyle K_{5}}$

أثبت روبرتسون وسيمور وتوماس (1993) التخمين لـ ،${\displaystyle k=6}$ باستخدام أيضًا نظرية الألوان الأربعة؛ فازت ورقتهم مع هذا الإثبات بجائزة فولكرسون لعام 1994. ويترتب على إثباتهم أن الرسوم البيانية القابلة للتضمين بدون ارتباط ، وهي نظير ثلاثي الأبعاد للرسوم البيانية المستوية، لها عدد لوني لا يزيد عن خمسة. ^[3] وبسبب هذه النتيجة، يُعرف أن التخمين صحيح لـ ،${\displaystyle k\leq 6}$ لكنه يظل دون حل لجميع .${\displaystyle k>6}$

بالنسبة لـ ، فإن بعض النتائج الجزئية معروفة: يجب أن يحتوي كل رسم بياني مكون من 7 ألوان على لون ثانوي أو لون ثانوي وآخر ثانوي. ^[4]${\displaystyle k=7}$${\displaystyle K_{7}}$${\displaystyle K_{4,4}}$${\displaystyle K_{3,5}}$

يحتوي كل رسم بياني على رأس به حواف متقابلة على الأكثر، ^[5] ومن هنا يتبع أن خوارزمية التلوين الجشعة التي تزيل هذا الرأس منخفض الدرجة، وتلون الرسم البياني المتبقي، ثم تضيف الرأس الذي تمت إزالته وتلونه، سوف تقوم بتلوين الرسم البياني المعطى بالألوان . ${\displaystyle G}$${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$

في ثمانينيات القرن العشرين، أثبت كل من ألكسندر ف. كوستوشكا ^[6] وأندرو توماسون ^[7] بشكل مستقل أن كل رسم بياني لا يحتوي على حدود ثانوية له درجة متوسطة وبالتالي يمكن تلوينه باستخدام الألوان. أدت سلسلة من التحسينات على هذا الحد إلى إثبات قابلية التلوين للرسوم البيانية التي لا تحتوي على حدود ثانوية. ^[8]${\displaystyle K_{k}}$${\textstyle O(k{\sqrt {\log k}})}$${\textstyle O(k{\sqrt {\log k}})}$${\displaystyle O(k\log \log k)}$${\displaystyle K_{k}}$

افترض جورجي هاجوس أن تخمين هادويجر يمكن تعزيزه إلى أقسام فرعية بدلاً من الأقسام الصغرى: أي أن كل رسم بياني به رقم لوني يحتوي على قسم فرعي من رسم بياني كامل . تخمين هاجوس صحيح بالنسبة لـ ، لكن كاتلين (1979) وجد أمثلة مضادة لهذا التخمين المعزز لـ ؛ تظل الحالات و مفتوحة. ^[9] لاحظ إردوس وفاجتلويز (1981) أن تخمين هاجوس يفشل بشدة بالنسبة للرسوم البيانية العشوائية : بالنسبة لأي ، في الحد حيث يذهب عدد الرؤوس ، إلى ما لا نهاية، فإن الاحتمال يقترب من واحد أن الرسم البياني العشوائي ذو الرأس - له رقم لوني ، وأن أكبر تقسيم فرعي لعشيرته له رؤوس. في هذا السياق، يجدر بالذكر أن الاحتمال يقترب أيضًا من أن يكون للرسم البياني العشوائي ذي الرأس رقم هادويجر أكبر من أو يساوي رقمه اللوني، وبالتالي فإن تخمين هادويجر ينطبق على الرسوم البيانية العشوائية ذات الاحتمالية العالية؛ وبشكل أكثر دقة، فإن رقم هادويجر يتناسب مع احتمالية عالية . ^[2]${\displaystyle k}$${\displaystyle K_{k}}$${\displaystyle k\leq 4}$${\displaystyle k\geq 7}$${\displaystyle k=5}$${\displaystyle k=6}$${\displaystyle \varepsilon >0}$${\displaystyle n}$${\displaystyle n}$${\displaystyle \geq ({\tfrac {1}{2}}-\varepsilon )n/\log _{2}n}$${\textstyle O({\sqrt {n}})}$${\displaystyle n}$${\textstyle n/{\sqrt {\log n}}}$

سأل بورويكي (1993) عما إذا كان من الممكن توسيع تخمين هادويجر ليشمل تلوين القائمة . بالنسبة لـ ،${\displaystyle k\leq 4}$ فإن كل رسم بياني برقم لوني للقائمة له مجموعة صغيرة من الرؤوس . ومع ذلك، فإن الحد الأقصى لعدد الألوان في القائمة للرسوم البيانية المستوية هو 5، وليس 4، وبالتالي فإن التمديد يفشل بالفعل بالنسبة للرسوم البيانية الخالية من الرؤوس الصغيرة . ^[10] وبشكل عام، بالنسبة لكل ، توجد رسوم بيانية يكون رقم هادويجر فيها هو وعدد الألوان في القائمة فيها هو . ^[11]${\displaystyle k}$${\displaystyle k}$${\displaystyle K_{5}}$${\displaystyle t\geq 1}$${\displaystyle 3t+1}$${\displaystyle 4t+1}$

افترض جيراردز وسيمور أن كل رسم بياني به رقم لوني له رسم بياني كامل كرقم فردي ثانوي . يمكن تمثيل مثل هذا الهيكل كعائلة من الأشجار الفرعية المنفصلة عن الرؤوس من ، كل منها ثنائي اللون، بحيث يكون كل زوج من الأشجار الفرعية متصلاً بحافة أحادية اللون. على الرغم من أن الرسوم البيانية التي لا تحتوي على رقم فردي ثانوي ليست بالضرورة متفرقة ، إلا أن حدًا أعلى مماثلًا ينطبق عليها كما هو الحال بالنسبة لتخمين هادويجر القياسي: الرسم البياني الذي لا يحتوي على رقم فردي ثانوي له رقم لوني . ^[12]${\displaystyle G}$${\displaystyle k}$${\displaystyle K_{k}}$${\displaystyle k}$${\displaystyle G}$${\displaystyle K_{k}}$${\displaystyle K_{k}}$${\textstyle \chi (G)=O{\bigl (}k{\sqrt {\log k}}{\bigr )}}$

من خلال فرض شروط إضافية على ، قد يكون من الممكن إثبات وجود قاصرين أكبر من . أحد الأمثلة على ذلك هو نظرية سنارك ، والتي تنص على أن كل رسم بياني مكعب يتطلب أربعة ألوان في أي تلوين للحافة يحتوي على رسم بياني بيترسن كقاصر، وقد افترضها دبليو تي توتي وأعلن روبرتسون وساندرز وسيمور وتوماس إثباتها في عام 2001. ^[13]${\displaystyle G}$${\displaystyle K_{k}}$