مؤشر الألوان الشامل للرسومات العشوائية

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