تلوين الحواف

في نظرية المخططات ، يُعرف تلوين حواف المخطط بأنه تخصيص " ألوان" لحواف المخطط بحيث لا تتشابه أي حافتين متصلتين في اللون. على سبيل المثال، يُظهر الشكل على اليمين تلوين حواف مخطط بالألوان الأحمر والأزرق والأخضر. يُعد تلوين الحواف أحد أنواع تلوين المخططات . وتطرح مسألة تلوين الحواف سؤالًا حول إمكانية تلوين حواف مخطط معين باستخدام $k$ لونًا مختلفًا على الأكثر، لقيمة معينة لـ $k$ ، أو باستخدام أقل عدد ممكن من الألوان. يُطلق على الحد الأدنى لعدد الألوان المطلوبة لحواف مخطط معين اسم مؤشر اللون للمخطط.

بحسب نظرية فيزينغ ، فإن عدد الألوان اللازمة لتلوين حواف رسم بياني بسيط هو إما درجته القصوى $Δ$ أو $Δ + 1.$ بالنسبة لبعض الرسوم البيانية، مثل الرسوم البيانية ثنائية الأجزاء والرسوم البيانية المستوية $ذات$ الدرجة العالية ، يكون عدد الألوان دائمًا $Δ$ ، أما بالنسبة للرسوم البيانية المتعددة ، فقد يصل عدد الألوان إلى $3Δ /2$ . توجد خوارزميات ذات زمن متعدد الحدود لإنشاء تلوينات مثلى للرسوم البيانية ثنائية الأجزاء، وتلوينات للرسوم البيانية البسيطة غير ثنائية الأجزاء تستخدم على الأكثر $Δ + 1$ لونًا؛ ومع ذلك، فإن المشكلة العامة المتمثلة في إيجاد تلوين أمثل للحواف هي مشكلة صعبة من نوع NP، وأسرع الخوارزميات المعروفة لها تستغرق زمنًا أُسّيًا. دُرست العديد من الاختلافات في مشكلة تلوين الحواف، حيث يجب أن تُلبي تعيينات الألوان للحواف شروطًا أخرى غير عدم التجاور. لتلوين الحواف تطبيقات في مشاكل الجدولة وفي تخصيص الترددات لشبكات الألياف الضوئية .

أمثلة

يمكن تلوين حواف الرسم البياني الدوري بلونين إذا كان طول الدورة زوجيًا: ببساطة يتم تبديل اللونين حول الدورة. أما إذا كان الطول فرديًا، فستكون هناك حاجة إلى ثلاثة ألوان. ^{[ 1 ]}

البناء الهندسي لتلوين 7 حواف للرسم البياني الكامل $K 8.$ كل فئة من فئات الألوان السبعة لها حافة واحدة من المركز إلى رأس مضلع، وثلاث حواف عمودية عليها.

يمكن تلوين حواف الرسم البياني الكامل K $ n$ $$ ذي n رأسًا باستخدام $n - 1$ لونًا عندما يكون $n$ عددًا زوجيًا ؛ وهذه حالة خاصة من نظرية باراني . يقدم سويفر (2008) البناء الهندسي التالي للتلوين في هذه الحالة: ضع $n$ نقطة عند رؤوس ومركز مضلع منتظم ذي $(n - 1)$ ضلعًا. لكل فئة لونية، أضف حافة واحدة من المركز إلى أحد رؤوس المضلع، وجميع الحواف العمودية التي تربط أزواج رؤوس المضلع. مع ذلك، عندما يكون $n$ فرديًا، يلزم $n$ لونًا: لا يمكن استخدام كل لون إلا لـ $(n - 1)/2$ حافة، أي جزء $1/ n$ من المجموع. ^{[ 2 ]}

درس العديد من الباحثين تلوين حواف الرسوم البيانية الفردية ، وهي رسوم بيانية منتظمة من الدرجة $n$ ، حيث تمثل الرؤوس فرقًا مكونة من $n - 1$ لاعبًا يتم اختيارهم من بين $2^n - 1$ لاعبًا، وتمثل الحواف احتمالات التزاوج بين هذه الفرق (مع بقاء لاعب واحد "غريب" لإدارة المباراة). في حالة $n = 3، نحصل على$ رسم بياني بيترسن المعروف . وكما أوضح بيغز (1972) المسألة (في حالة $n = 6$ )، يرغب اللاعبون في إيجاد جدول زمني لهذه التزاوجات بحيث يلعب كل فريق مبارياته الست في أيام مختلفة من الأسبوع، مع يوم راحة لجميع الفرق يوم الأحد؛ أي، بتعبير رياضي، يرغبون في إيجاد تلوين بستة حواف للرسم البياني الفردي المنتظم من الدرجة 6 $O6 .$ عندما تكون $قيمة n$ هي 3 أو 4 أو 8، فإن تلوين حواف $O n$ يتطلب $n + 1$ لونًا، ولكن عندما تكون قيمتها 5 أو 6 أو 7، فإن $n$ لونًا فقط مطلوبة. ^{[ 3 ]}

التعريفات

كما هو الحال مع تلوين الرؤوس ، يُفترض دائمًا أن تلوين حواف الرسم البياني، عند ذكره دون أي تحديد، هو تلوين صحيح للحواف، أي أنه لا يتم تخصيص اللون نفسه لحواف متجاورة. هنا، تُعتبر حافتان مختلفتان متجاورتين عندما تشتركان في رأس واحد. ويمكن أيضًا اعتبار تلوين حواف الرسم البياني $G مكافئًا لتلوين رؤوس$ الرسم البياني الخطي $L (G)$ ، وهو الرسم البياني الذي يحتوي على رأس لكل حافة من حواف $G$ وحافة لكل زوج من الحواف المتجاورة في $G.$

يُطلق على تلوين الحواف الصحيح باستخدام $k$ لونًا مختلفًا اسم تلوين الحواف الصحيح من الرتبة $k$ . ويُقال إن الرسم البياني الذي يمكن تلوين حوافه من الرتبة $k قابل للتلوين من الرتبة$ $k$ . أصغر عدد من الألوان اللازمة لتلوين حواف الرسم البياني $G$ بشكل صحيح هو مؤشر اللون ، أو عدد ألوان الحواف، $χ$ $' (G) .$ يُكتب مؤشر اللون أحيانًا باستخدام الرمز $χ₁ (G)$ ؛ في هذا الرمز، يشير الرقم السفلي 1 إلى أن الحواف كائنات أحادية البعد. يكون الرسم البياني ملونًا من الرتبة $k$ إذا كان مؤشر لونه يساوي $k$ بالضبط . يجب عدم الخلط بين مؤشر اللون وعدد الألوان χ $(G)$ أو $χ₀ (G) ، وهو$ الحد الأدنى لعدد الألوان اللازمة لتلوين رؤوس الرسم البياني $G$ بشكل صحيح .

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

العلاقة بالمطابقة

يحتوي هذا الرسم البياني المستوي المنتظم من الدرجة 3 على 16 رأسًا و24 ضلعًا، ولكن 7 أضلاع فقط تُستخدم في أي عملية مطابقة قصوى. لذلك، يتطلب الأمر أربعة ألوان في أي عملية تلوين للأضلاع.

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

إذا كان حجم التطابق الأقصى في رسم بياني معين صغيرًا، فسيلزم عدد كبير من التطابقات لتغطية جميع حواف الرسم البياني. وبصورة أكثر دقة، يشير هذا المنطق إلى أنه إذا كان للرسم البياني $m$ حافة إجمالًا، وإذا كان الحد الأقصى لعدد الحواف التي يمكن أن تنتمي إلى تطابق أقصى $هو β$ حافة على الأكثر، فيجب أن يستخدم كل تلوين لحواف الرسم البياني ما لا يقل عن $m / β$ لونًا مختلفًا. ^{[ 4 ]} على سبيل المثال، يحتوي الرسم البياني المستوي ذو 16 رأسًا الموضح في الرسم التوضيحي على $m = 24$ حافة. في هذا الرسم البياني، لا يمكن أن يكون هناك تطابق تام؛ لأنه إذا تمت مطابقة الرأس المركزي، فقد يتم تجميع الرؤوس المتبقية غير المتطابقة في ثلاثة مكونات متصلة مختلفة تحتوي على أربعة وخمسة وخمسة رؤوس على التوالي، ولا يمكن مطابقة المكونات ذات العدد الفردي من الرؤوس بشكل تام. ومع ذلك، يحتوي الرسم البياني على تطابقات قصوى بسبع حواف، لذا فإن $β = 7$ . لذلك، فإن عدد الألوان اللازمة لتلوين حواف الرسم البياني هو 24/7 على الأقل، وبما أن عدد الألوان يجب أن يكون عددًا صحيحًا، فهو أربعة على الأقل.

بالنسبة للرسم البياني المنتظم من الدرجة $k$ الذي لا يحتوي على تطابق تام، يمكن استخدام هذا الحد الأدنى لإثبات الحاجة إلى $k + 1 لونًا على الأقل.$ ^{[ 4 ]} وينطبق هذا بشكل خاص على الرسم البياني المنتظم ذي عدد فردي من الرؤوس (مثل الرسوم البيانية الكاملة الفردية)؛ ففي هذه الرسوم البيانية، وبحسب مبرهنة المصافحة ، يجب أن تكون قيمة $k$ زوجية. مع ذلك، لا تفسر المتباينة $χ' \geq m / β$ بشكل كامل مؤشر التلوين لكل رسم بياني منتظم، لوجود رسوم بيانية منتظمة تحتوي على تطابقات تامة ولكنها غير قابلة للتلوين بـ k حافة. على سبيل المثال، الرسم البياني Petersen منتظم، حيث $m = 15$ و $β = 5$ حواف في تطابقاته التامة، ولكنه لا يحتوي على تلوين بثلاث حواف.

العلاقة بالدرجة

نظرية فيزينغ

يرتبط عدد الألوان للحواف في الرسم البياني $G ارتباطًا وثيقًا$ بالدرجة القصوى $Δ(G)$ ، وهي أكبر عدد من الحواف المتصلة بأي رأس منفرد في $G.$ من الواضح أن $χ' (G) \geq Δ(G)$ ، لأنه إذا التقت $Δ حافة مختلفة عند الرأس$ $v$ نفسه ، فيجب تخصيص ألوان مختلفة لكل حافة، وهذا لا يمكن تحقيقه إلا إذا كان هناك على الأقل $Δ$ لونًا متاحًا للتخصيص. تنص نظرية فيزينغ (نسبةً إلى فاديم ج. فيزينغ الذي نشرها عام 1964) على أن هذا الحد دقيق للغاية: لأي رسم بياني، يكون عدد الألوان للحواف إما $Δ(G)$ أو $Δ(G) + 1.$ عندما $χ' (G) = Δ(G)$ ، يُقال إن G من الفئة 1؛ وإلا، يُقال إنه من الفئة 2.

كل رسم بياني ثنائي الأجزاء ينتمي إلى الفئة 1، ^{[ 5 ]} ومعظم الرسوم البيانية العشوائية تنتمي إلى الفئة 1. ^[⁶^] ومع ذلك، فإن تحديد ما إذا كان رسم بياني عشوائي ينتمي إلى الفئة 1 هو مسألة NP-كاملة . ^[⁷^]

أثبت فيزينغ (1965) أن الرسوم البيانية المستوية ذات الدرجة القصوى ثمانية على الأقل تنتمي إلى الفئة الأولى، وافترض أن الأمر نفسه ينطبق على الرسوم البيانية المستوية ذات الدرجة القصوى سبعة أو ستة. من جهة أخرى، توجد رسوم بيانية مستوية ذات درجة قصوى تتراوح من اثنين إلى خمسة تنتمي إلى الفئة الثانية. وقد تم إثبات هذا الافتراض لاحقًا للرسوم البيانية ذات الدرجة القصوى سبعة. ^{[ 8 ]} جميع الرسوم البيانية المكعبة المستوية عديمة الجسور تنتمي إلى الفئة الأولى؛ وهذا شكل مكافئ لنظرية الألوان الأربعة . ^[⁹^]

الرسوم البيانية المنتظمة

يُعدّ التحليل الأحادي للرسم البياني المنتظم من الرتبة k ، أي تقسيم حواف الرسم البياني إلى تطابقات تامة ، هو نفسه تلوين حواف الرسم البياني من الرتبة k . بمعنى آخر، يكون للرسم البياني المنتظم تحليل أحادي إذا وفقط إذا كان من الفئة 1. وكحالة خاصة من ذلك، يُطلق أحيانًا على تلوين حواف الرسم البياني المكعب (المنتظم من الرتبة 3) من الرتبة 3 اسم تلوين تايت .

لا يمتلك كل رسم بياني منتظم تحليلًا إلى عوامل من الدرجة الأولى؛ على سبيل المثال، لا يمتلك رسم بيترسن هذا التحليل. وبشكل أعم، تُعرَّف الرسوم البيانية غير المنتظمة (snarks) بأنها الرسوم البيانية التي، مثل رسم بيترسن، لا تحتوي على جسور، ومنتظمة من الدرجة الثالثة، ومن الفئة الثانية.

بحسب نظرية كونيغ (1916) ، فإن كل رسم بياني منتظم ثنائي الأجزاء له تحليل إلى عوامل من الدرجة الأولى. وقد ذُكرت النظرية سابقًا بدلالة التكوينات الإسقاطية ، وأثبتها إرنست شتاينيتز .

الرسوم البيانية المتعددة

رسم بياني متعدد من نوع شانون بدرجة ستة وتعدد حواف ثلاثة، ويتطلب تسعة ألوان في أي تلوين للحواف.

بالنسبة للرسوم البيانية المتعددة ، حيث قد تربط عدة حواف متوازية نفس الرأسين، توجد نتائج مشابهة لنظرية فيزينغ، ولكنها أضعف منها، تربط بين العدد اللوني للحافة $χ' (G)$ ، والدرجة القصوى $Δ(G)$ ، والتعددية $μ(G)$ ، أي الحد الأقصى لعدد الحواف في أي حزمة من الحواف المتوازية. كمثال بسيط يوضح أن نظرية فيزينغ لا تُعمم على الرسوم البيانية المتعددة، لنأخذ رسمًا بيانيًا متعددًا من نوع شانون ، وهو رسم بياني متعدد بثلاثة رؤوس وثلاث حزم من $μ(G)$ من الحواف المتوازية التي تربط كل زوج من الرؤوس الثلاثة. في هذا المثال، $Δ(G) = 2μ(G)$ (حيث يتصل كل رأس بحزمتين فقط من أصل ثلاث حزم من الحواف المتوازية التي $يبلغ عددها μ(G)$ )، لكن عدد الألوان للحواف هو $3μ(G)$ (يوجد $3μ(G)$ حافة إجمالاً، وكل حافتين متجاورتان، لذا يجب أن تُخصص ألوان مختلفة لكل حافة). في نتيجة ألهمت فيزينغ، ^{[ 10 ]} أثبت شانون (1949) أن هذه هي أسوأ حالة: $χ' (G) \leq (3/2)Δ(G)$ لأي رسم بياني متعدد $G.$ بالإضافة إلى ذلك، لأي رسم بياني متعدد $G$ ، $χ' (G) \leq Δ(G) + μ(G)$ ، وهي متباينة تُختزل إلى نظرية فيزينغ في حالة الرسوم البيانية البسيطة (حيث $μ(G) = 1$ ).

الخوارزميات

نظرًا لأن مشكلة اختبار ما إذا كان الرسم البياني من الفئة 1 هي مسألة NP-كاملة ، فلا توجد خوارزمية معروفة ذات زمن متعدد الحدود لتلوين حواف كل رسم بياني بالعدد الأمثل من الألوان. ومع ذلك، فقد طُوِّر عدد من الخوارزميات التي تُخفف واحدًا أو أكثر من هذه المعايير: فهي تعمل فقط على مجموعة فرعية من الرسوم البيانية، أو أنها لا تستخدم دائمًا العدد الأمثل من الألوان، أو أنها لا تعمل دائمًا في زمن متعدد الحدود.

تلوين فئات خاصة من الرسوم البيانية على النحو الأمثل

في حالة الرسوم البيانية ثنائية الأجزاء أو الرسوم البيانية المتعددة ذات الدرجة القصوى $Δ$ ، يكون العدد الأمثل للألوان هو $Δ$ بالضبط . وقد أظهر كول وأوست وشيرا (2001) أنه يمكن إيجاد تلوين أمثل لحواف هذه الرسوم البيانية في زمن شبه خطي $O(m log Δ)$ ، حيث $m$ هو عدد الحواف في الرسم البياني. وصف كول وهوبكروفت (1982) وألون (2003) خوارزميات أبسط، ولكنها أبطأ نوعًا ما. تبدأ خوارزمية ألون (2003) بجعل الرسم البياني المُدخل منتظمًا، دون زيادة درجته أو حجمه بشكل ملحوظ، وذلك بدمج أزواج الرؤوس التي تنتمي إلى نفس جانب التقسيم الثنائي، ثم إضافة عدد قليل من الرؤوس والحواف الإضافية. بعد ذلك، إذا كانت الدرجة فردية، يجد ألون تطابقًا تامًا واحدًا في زمن شبه خطي، ويُخصص له لونًا، ثم يُزيله من الرسم البياني، مما يجعل الدرجة زوجية. أخيرًا، يطبق ألون ملاحظةً لجابو (1976) ، مفادها أن اختيار مجموعات فرعية متناوبة من الحواف في جولة أويلر للرسم البياني يقسمه إلى رسمين بيانيين فرعيين منتظمين، لتقسيم مشكلة تلوين الحواف إلى مشكلتين فرعيتين أصغر، ويحل خوارزميته هاتين المشكلتين الفرعيتين بشكل تكراري . يبلغ إجمالي وقت خوارزميته $O(m log m)$ .

بالنسبة للرسوم البيانية المستوية ذات الدرجة القصوى $Δ \geq 7$ ، يكون العدد الأمثل للألوان هو $Δ$ بالضبط . وبافتراض أقوى وهو أن $Δ \geq 9$ ، فمن الممكن إيجاد تلوين أمثل للحواف في وقت خطي ( كول وكواليك 2008 ) .

بالنسبة للرسوم البيانية المنتظمة من النوع d والتي تعتبر عشوائية زائفة بمعنى أن مصفوفة التجاور الخاصة بها لها ثاني أكبر قيمة ذاتية ( بالقيمة المطلقة ) على الأكثر $d 1-ε$ ، فإن d هو العدد الأمثل للألوان ( Ferber & Jain 2020 ) .

الخوارزميات التي تستخدم عددًا من الألوان يفوق العدد الأمثل

يصف كل من Misra & Gries (1992) و Gabow et al. (1985) خوارزميات الوقت متعدد الحدود لتلوين أي رسم بياني بـ $Δ + 1$ لونًا، بما يتوافق مع الحد الذي تحدده نظرية Vizing؛ انظر خوارزمية تلوين الحواف Misra & Gries .

بالنسبة للرسوم البيانية المتعددة، قدم كارلوف وشمويز (1987) الخوارزمية التالية، والتي نسبوها إلى إيلي أوبفال . اجعل الرسم البياني المتعدد المدخل $G رسمًا بيانيًا$ أويلريًا بإضافة رأس جديد متصل بحافة بكل رأس ذي درجة فردية، ثم ابحث عن مسار أويلري، واختر اتجاهًا لهذا المسار. شكّل رسمًا بيانيًا ثنائي الأجزاء $H$ يحتوي على نسختين من كل رأس في $G$ ، واحدة على كل جانب من التقسيم الثنائي، مع وجود حافة من الرأس $u$ على الجانب الأيسر من التقسيم الثنائي إلى الرأس $v$ على الجانب الأيمن من التقسيم الثنائي كلما كان للمسار الموجه حافة من $u$ إلى $v$ في $G.$ طبّق خوارزمية تلوين حواف الرسم البياني ثنائي الأجزاء على $H.$ يتوافق كل لون في $H$ مع مجموعة من الحواف في $G$ التي تُشكّل رسمًا بيانيًا فرعيًا بدرجة قصوى اثنين؛ أي اتحادًا منفصلًا للمسارات والدورات، لذا لكل لون في $H،$ من الممكن تشكيل ثلاثة ألوان في $G.$ يُحدَّد وقت تنفيذ الخوارزمية بوقت تلوين حواف الرسم البياني ثنائي الأجزاء، وهو $O(m log Δ)$ باستخدام خوارزمية كول، أوست ، وشيرا (2001) . ويبلغ عدد الألوان التي تستخدمها هذه الخوارزمية على الأكثر $3\left\lceil {\frac {\Delta }{2}}\right\rceil$ قريب من حد شانون، ولكنه ليس مطابقًا له تمامًا. $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$ يمكن أيضًا تحويلها إلى خوارزمية متوازية بطريقة مباشرة. في الورقة البحثية نفسها، يقدم كارلوف وشمويز خوارزمية خطية لتلوين الرسوم البيانية المتعددة ذات الدرجة القصوى 3 بأربعة ألوان (مطابقة لحدود شانون وفايزينغ) تعمل وفق مبادئ مماثلة: تضيف خوارزميتهم رأسًا جديدًا لجعل الرسم البياني أويلريًا، ثم تجد مسارًا أويلريًا، ثم تختار مجموعات متناوبة من الحواف على المسار لتقسيم الرسم البياني إلى رسمين بيانيين فرعيين ذوي درجة قصوى 2. يمكن تلوين المسارات والدورات الزوجية لكل رسم بياني فرعي بلونين. بعد هذه الخطوة، تحتوي كل دورة فردية متبقية على حافة واحدة على الأقل يمكن تلوينها بأحد اللونين المستخدمين في الرسم البياني الفرعي المقابل. يؤدي إزالة هذه الحافة من الدورة الفردية إلى ترك مسار، يمكن تلوينه باستخدام اللونين المستخدمين في الرسم البياني الفرعي الخاص به.

قد تستخدم خوارزمية التلوين الجشعة ، التي تُعالج حواف الرسم البياني أو الرسم البياني المتعدد واحدة تلو الأخرى، وتُخصص لكل حافة أول لون متاح ، ما يصل إلى $2Δ - 1$ لونًا، أي ما يقارب ضعف عدد الألوان اللازمة. مع ذلك، تتميز هذه الخوارزمية بإمكانية استخدامها في بيئة الخوارزميات الفورية حيث يكون الرسم البياني المُدخل غير معروف مسبقًا؛ في هذه الحالة، تبلغ نسبة تنافسيتها 2، وهي النسبة المثلى: إذ لا تستطيع أي خوارزمية فورية أخرى تحقيق أداء أفضل. ^{[ 11 ]} أما إذا وصلت الحواف بترتيب عشوائي، وكان للرسم البياني المُدخل درجة لوغاريتمية على الأقل، فيمكن تحقيق نسب تنافسية أصغر. ^{[ 12 ]}

وضع العديد من المؤلفين تخمينات تشير إلى أن المؤشر اللوني الكسري لأي رسم بياني متعدد (وهو عدد يمكن حسابه في وقت متعدد الحدود باستخدام البرمجة الخطية ) يقع ضمن نطاق واحد من المؤشر اللوني. ^{[ 13 ]} إذا صحت هذه التخمينات، فسيكون من الممكن حساب عدد لا يختلف عن المؤشر اللوني بأكثر من واحد في حالة الرسم البياني المتعدد، وهو ما يتوافق مع ما هو معروف من خلال نظرية فيزينغ للرسوم البيانية البسيطة. على الرغم من عدم إثباتها بشكل عام، إلا أنه من المعروف أن هذه التخمينات صحيحة عندما يكون المؤشر اللوني على الأقل $\Delta +{\sqrt {\Delta /2}}$ ، كما يمكن أن يحدث بالنسبة للرسوم البيانية المتعددة ذات التعددية الكبيرة بما فيه الكفاية. ^{[ 14 ]}

خوارزميات دقيقة

من السهل اختبار ما إذا كان من الممكن تلوين حواف الرسم البياني بلون واحد أو لونين، لذا فإن أول حالة غير بديهية لتلوين الحواف هي اختبار ما إذا كان الرسم البياني يحتوي على تلوين ثلاثي للحواف. وكما أوضح كواليك (2009) ، من الممكن اختبار ما إذا كان الرسم البياني يحتوي على تلوين ثلاثي للحواف في زمن قدره $O(1.344 n)$ ، باستخدام مساحة متعددة الحدود فقط. على الرغم من أن هذا الحد الزمني أُسّي، إلا أنه أسرع بكثير من البحث الشامل عن جميع التخصيصات الممكنة للألوان للحواف. كل رسم بياني ثنائي الاتصال منتظم من الدرجة 3 ذو $n$ رأسًا يحتوي على $O(2 n /2)$ من التلوينات ثلاثية الحواف؛ ويمكن سردها جميعًا في زمن قدره $O(2 n /2)$ (أبطأ قليلاً من زمن العثور على تلوين واحد). كما لاحظ جريج كوبربيرج ، فإن الرسم البياني لمنشور فوق مضلع ذي $n /2$ ضلعًا يحتوي على $Ω(2 n /2)$ تلوينًا (الحد الأدنى بدلاً من الحد الأعلى)، مما يدل على أن هذا الحد دقيق. ^{[ 15 ]}

By applying exact algorithms for vertex coloring to the line graph of the input graph, it is possible to optimally edge-color any graph with $m$ edges, regardless of the number of colors needed, in time $2 m m O(1)$ and exponential space, or in time $O(2.2461 m)$ and only polynomial space (Björklund, Husfeldt & Koivisto 2009).

Because edge coloring is NP-complete even for three colors, it is unlikely to be fixed parameter tractable when parametrized by the number of colors. However, it is tractable for other parameters. In particular, Zhou, Nakano & Nishizeki (1996) showed that for graphs of treewidth $w$ , an optimal edge coloring can be computed in time $O(nw (6 w) w (w + 1)/2)$ , a bound that depends superexponentially on $w$ but only linearly on the number $n$ of vertices in the graph.

Nemhauser & Park (1991) formulate the edge coloring problem as an integer program and describe their experience using an integer programming solver to edge color graphs. However, they did not perform any complexity analysis of their algorithm.

Additional properties

يُقال إن الرسم البياني قابل للتلوين $بـ k حافة$ بشكل فريد إذا كانت هناك طريقة واحدة فقط لتقسيم الحواف إلى $k$ فئة لونية، مع تجاهل $k$ $!$ من التباديل الممكنة للألوان. بالنسبة لـ $k$ $\neq 3$ ، فإن الرسوم البيانية الوحيدة القابلة للتلوين $بـ k حافة بشكل فريد هي المسارات والدورات$ والنجوم ، ولكن بالنسبة لـ $k$ $= 3$ ، قد تكون هناك رسوم بيانية أخرى قابلة للتلوين $بـ k حافة بشكل فريد. كل رسم بياني قابل للتلوين بـ 3 حواف بشكل فريد يحتوي على ثلاث$ دورات هاميلتونية بالضبط (تتشكل بحذف إحدى فئات الألوان الثلاث)، ولكن توجد رسوم بيانية منتظمة من الدرجة 3 تحتوي على ثلاث دورات هاميلتونية وليست قابلة للتلوين بـ 3 ألوان بشكل فريد، مثل رسوم بيترسن المعممة $G$ $(6n$ $+$ $3, 2)$ لـ $n$ $\geq 2.$ الرسم البياني الوحيد غير المستوي المعروف القابل للتلوين بـ 3 ألوان بشكل فريد هو رسم بيترسن المعمم $G$ $(9,2)$ ، وقد تم التكهن بأنه لا توجد رسوم بيانية أخرى. ^[¹⁶^]

درس فولكمان وفولكرسون (1969) المتتاليات غير المتزايدة للأعداد $m₁, m₂, m₃, ...، والتي$ تتميز بوجود تلوين مناسب لحواف الرسم البياني $G،$ $حيث$ يكون $m₁$ $حافة$ باللون الأول، $وm₂ حافة باللون الثاني$ ، وهكذا. ولاحظا أنه إذا كانت المتتالية $P$ ممكنة بهذا المعنى، وكانت أكبر في الترتيب المعجمي من متتالية $Q$ لها نفس المجموع، فإن $Q$ تكون ممكنة أيضًا. فإذا كانت $P > Q$ في الترتيب المعجمي، فإنه يمكن تحويل $P إلى$ $Q عبر سلسلة من الخطوات، كل$ $خطوة$ منها تُقلل أحد الأعداد $mᵢ$ بمقدار وحدة واحدة، وتزيد عددًا آخر $mⱼ$ حيث $i <$ $j$ بمقدار وحدة واحدة. وفيما يتعلق بتلوين الحواف، بدءًا من تلوين يحقق $P$ ، يمكن تنفيذ كل خطوة من هذه الخطوات نفسها عن طريق تبديل اللونين $i$ و $j$ على سلسلة كيمبي ، $وهي$ مسار أقصى من الحواف التي تتناوب بين اللونين. على وجه الخصوص، أي رسم بياني له تلوين حواف متساوي ، وهو تلوين حواف بعدد مثالي من الألوان حيث يختلف كل فئتين لونيتين في الحجم بوحدة واحدة على الأكثر.

يمكن استخدام نظرية دي بروين-إردوش لنقل العديد من خصائص تلوين الحواف من الرسوم البيانية المحدودة إلى الرسوم البيانية غير المحدودة . على سبيل المثال، يمكن تعميم نظريتي شانون وفايزينغ، اللتين تربطان درجة الرسم البياني بمؤشره اللوني، بشكل مباشر على الرسوم البيانية غير المحدودة. ^{[ 17 ]}

يتناول ريختر (2011) مشكلة إيجاد رسم بياني لمخطط مكعب مُعطى ، بحيث يكون لكل حافة من حواف الرسم أحد ثلاثة ميول مختلفة، ولا تقع أي حافتين على خط مستقيم واحد. إذا وُجد مثل هذا الرسم، فمن الواضح أنه يمكن استخدام ميول الحواف كألوان في تلوين ثلاثي الحواف للمخطط. على سبيل المثال، يُمثل رسم مخطط المنفعة $K 3,3$ ، باستخدام حواف وأقطار سداسي منتظم، تلوينًا ثلاثي الحواف للمخطط بهذه الطريقة. وكما يُبين ريختر، فإن مخططًا ثنائي الأجزاء بسيطًا منتظمًا ثلاثيًا، مع تلوين تايت مُعطى، له رسم من هذا النوع يُمثل التلوين المُعطى إذا وفقط إذا كان المخطط متصلًا ثلاثي الحواف . بالنسبة للرسم البياني غير الثنائي، يكون الشرط أكثر تعقيدًا بعض الشيء: يمكن تمثيل تلوين معين برسم إذا كان الغطاء المزدوج الثنائي للرسم البياني متصلًا بثلاثة حواف، وإذا أدى حذف أي زوج من الحواف أحادية اللون إلى رسم بياني فرعي لا يزال غير ثنائي. يمكن اختبار هذه الشروط بسهولة في وقت متعدد الحدود؛ ومع ذلك، فإن مشكلة اختبار ما إذا كان للرسم البياني المنتظم رباعي الألوان ذي الحواف الأربعة رسم بحواف ذات أربعة ميول، تمثل الألوان بالميول، هي مشكلة كاملة بالنسبة لنظرية الوجود للأعداد الحقيقية ، وهي فئة تعقيد لا تقل صعوبة عن كونها NP-كاملة.

بالإضافة إلى ارتباطه بالدرجة القصوى وعدد التطابقات القصوى للرسم البياني، يرتبط مؤشر اللون ارتباطًا وثيقًا بالتشعب الخطي $la(G)$ للرسم البياني $G$ ، وهو الحد الأدنى لعدد الغابات الخطية (اتحادات منفصلة من المسارات) التي يمكن تقسيم حواف الرسم البياني إليها. التطابق هو نوع خاص من الغابات الخطية، وفي الاتجاه الآخر، يمكن تلوين أي غابة خطية بلونين للحواف، لذا فإنه لكل $G$ ، يترتب على ذلك أن $la(G) \leq χ' (G) \leq 2la(G)$ . تنص فرضية أكياما (المسماة على اسم جين أكياما ) على أن $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil$ ومن ثمّ يتبين بقوة أكبر أن $2 la(G) - 2 \leq χ' (G) \leq 2 la(G)$ . بالنسبة للرسوم البيانية ذات الدرجة القصوى ثلاثة، $فإن la(G)$ تساوي دائمًا اثنين بالضبط، لذا في هذه الحالة يتطابق الحد $χ' (G) \leq 2 la(G)$ مع الحد الذي تنص عليه نظرية فيزينغ. ^{[ 18 ]}

أنواع أخرى

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

تُعرَّف خاصية التفرع في الرسم البياني بأنها الحد الأدنى لعدد الألوان اللازمة لضمان عدم وجود دورات بين حواف كل لون (بدلاً من عدم وجود أزواج متجاورة من الحواف في مسألة تلوين الحواف القياسية). أي أنها الحد الأدنى لعدد الغابات التي يمكن تقسيم حواف الرسم البياني إليها. ^{[ 19 ]} وعلى عكس مؤشر اللون، يمكن حساب خاصية التفرع في الرسم البياني في وقت متعدد الحدود. ^{[ 20 ]}

تلوين حواف القوائم هو مسألة تُعطى فيها رسمة بيانية، حيث ترتبط كل حافة بقائمة ألوان، والمطلوب إيجاد تلوين مناسب للحواف بحيث يُستمد لون كل حافة من قائمة ألوانها. يُعرَّف مؤشر التلوين القائم على القوائم للرسمة البيانية $G$ بأنه أصغر عدد $k$ بحيث، بغض النظر عن كيفية اختيار قوائم ألوان الحواف، طالما أن كل حافة تحتوي على $k$ لونًا على الأقل في قائمتها، فإن التلوين مضمون. وبالتالي، فإن مؤشر التلوين القائم على القوائم يكون دائمًا أكبر من أو يساوي مؤشر التلوين. يمكن إعادة صياغة حدسية دينيتز حول إكمال المربعات اللاتينية الجزئية على النحو التالي: إن عدد التلوين القائم على القوائم للحواف للرسمة البيانية الثنائية الكاملة $K n,n$ يساوي عدد التلوين القائم على الحواف $n$ . وقد حلّ غالڤين (1995) هذه الحدسية بإثباته، بشكل أعم، أن مؤشر التلوين ومؤشر التلوين القائم على القوائم متساويان في كل رسمة بيانية ثنائية. وقد تم افتراض أن المساواة بين المؤشر اللوني ومؤشر القائمة اللوني صحيحة، وبشكل أكثر عمومية، بالنسبة للرسوم البيانية المتعددة العشوائية بدون حلقات ذاتية؛ هذا الافتراض لا يزال مفتوحًا.

تم توسيع نطاق العديد من أشكال تلوين الرؤوس الشائعة الأخرى لتشمل تلوين الحواف. على سبيل المثال، يُعد تلوين الحواف الكامل شكلاً من أشكال التلوين الكامل ، وهو تلوين حواف مناسب حيث يجب تمثيل كل زوج من الألوان بزوج واحد على الأقل من الحواف المتجاورة، ويكون الهدف منه زيادة العدد الإجمالي للألوان إلى أقصى حد. ^{[ 21 ]} أما تلوين الحواف القوي فهو شكل من أشكال التلوين القوي ، وهو تلوين حواف يجب أن يكون لكل حافتين متجاورتين لونان مختلفان. ^{[ 22 ]} ويُستخدم تلوين الحواف القوي في مخططات تخصيص القنوات للشبكات اللاسلكية . ^{[ 23 ]}

تلوين الحواف غير الدوري هو نوع من تلوين الحواف غير الدوري ، حيث يشكل كل لونين معًا رسمًا بيانيًا فرعيًا غير دوري (أي غابة). ^{[ 24 ]} مؤشر التلوين غير الدوري للرسم البياني $G$ ، ويرمز إليه بـ $a'(G)$ ، هو أقل عدد من الألوان اللازمة للحصول على تلوين حواف غير دوري مناسب لـ $G$ وقد تم التكهن بأن $a'(G)\leq \Delta +2$ ، أين $\Delta$ هي أقصى درجة من $G$ [ ²⁵^{] حاليًا}^، أفضل ربط معروف هو $a'(G)\leq \lceil 3.74(\Delta -1)\rceil$ [ ^{26 ] تصبح} المشكلة أسهل عندما $G$ له محيط كبير . وبشكل أكثر تحديدًا، هناك ثابت $c$ بحيث إذا كان محيط $G$ هو على الأقل $c\Delta \log \Delta$ ، ثم $a'(G)\leq \Delta +2$ [ ^{27 ]} نتيجة مماثلة هي أنه بالنسبة ^للجميع $\epsilon >0$ يوجد $g$ بحيث إذا $G$ له محيط على الأقل $g$ ، ثم $a'(G)\leq (1+\epsilon )\Delta$ [ ²⁸^]

درس إبستين (2013) تلوين ثلاثة حواف للرسوم البيانية المكعبة، مع خاصية إضافية تتمثل في عدم اشتراك أي دورتين ثنائيتي اللون في أكثر من حافة واحدة. وأظهر أن وجود هذا التلوين يُكافئ وجود رسم للرسم البياني على شبكة ثلاثية الأبعاد، بحواف موازية لمحاور الإحداثيات، وكل خط موازٍ للمحاور يحتوي على رأسين على الأكثر. مع ذلك، وكما هو الحال في مسألة تلوين ثلاثة حواف القياسية، فإن إيجاد تلوين من هذا النوع يُعد مسألة NP-كاملة.

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

إذا كان الرسم البياني المنتظم ثلاثي الأبعاد على سطح ما ملونًا بثلاثة ألوان للحواف، فإن الرسم البياني الثنائي له يُشكل مثلثًا على السطح نفسه، وهو ملون أيضًا للحواف (وإن لم يكن، بشكل عام، ملونًا بشكل صحيح)، بحيث يكون لكل مثلث حافة واحدة من كل لون. يمكن استخدام ألوان واتجاهات أخرى للمثلثات، مع قيود محلية أخرى على كيفية ترتيب الألوان عند رؤوس أو أوجه المثلث، لترميز أنواع عديدة من الأشكال الهندسية. على سبيل المثال، يمكن وصف التقسيمات المستطيلة (تقسيمات التقسيم المستطيل إلى مستطيلات أصغر، حيث تلتقي ثلاثة مستطيلات عند كل رأس) بشكل توافقي بواسطة "التسمية المنتظمة"، وهي تلوين ثنائي لحواف المثلث الثنائي للتقسيم، مع القيد القائل بأن الحواف المتصلة بكل رأس تُشكل أربع متواليات فرعية متجاورة، تكون الألوان داخل كل منها متطابقة. هذا التصنيف ثنائي لتلوين التقسيم المستطيل نفسه، حيث تكون الحواف الرأسية بلون والحواف الأفقية بلون آخر. ويمكن استخدام قيود محلية مماثلة على ترتيب ظهور الحواف الملونة حول رأس ما لترميز تضمينات الشبكة الخطية للرسوم البيانية المستوية والمجسمات ثلاثية الأبعاد ذات الأضلاع المتوازية مع المحاور. بالنسبة لكل نوع من هذه الأنواع الثلاثة من التصنيفات المنتظمة، تشكل مجموعة التصنيفات المنتظمة لرسم بياني ثابت شبكة توزيعية يمكن استخدامها لسرد جميع البنى الهندسية المستندة إلى الرسم البياني نفسه بسرعة (مثل جميع المجسمات متعددة الأوجه المتوازية مع المحاور التي لها الهيكل نفسه) أو لإيجاد بنى تُحقق قيودًا إضافية. ^{[ 29 ]}

يمكن تفسير الأوتوماتون المحدود الحتمي على أنه رسم بياني موجه ، حيث يمتلك كل رأس فيه نفس درجة الخروج $d$ ، وتكون حوافه ملونة $بـ d$ لونًا بحيث يكون لكل حافتين لهما نفس رأس المصدر لونان مختلفان. تُعرف مسألة تلوين المسارات بأنها مسألة تلوين حواف رسم بياني موجه ذي درجات خروج متساوية، بحيث يمتلك الأوتوماتون الناتج كلمة تزامن . وقد حلّ تراهتمان (2009) مسألة تلوين المسارات بإثبات إمكانية إيجاد هذا التلوين كلما كان الرسم البياني المعطى متصلًا بقوة وغير دوري .

تتعلق نظرية رامزي بمسألة $تلوين$ حواف الرسم البياني الكامل الكبير $K n بـ k$ لونًا لتجنب إنشاء رسوم بيانية جزئية كاملة أحادية اللون $K s$ بحجم معين $s$ . وفقًا للنظرية، يوجد عدد $R$ $k$ $($ $s$ $)$ بحيث أنه كلما $كان n$ $\geq$ $R$ $($ $s$ $)$ ، يصبح هذا التلوين غير ممكن. على سبيل المثال، $R$ $k$ $(s) = 6$ ، أي أنه إذا تم تلوين حواف الرسم البياني $K$ $s$ بلونين، فسيكون هناك دائمًا مثلث أحادي اللون.

يُقال عن مسار في رسم بياني مُلوَّن الحواف أنه مسار قوس قزح إذا لم يتكرر أي لون عليه. ويُقال عن الرسم البياني أنه مُلوَّن بألوان قوس قزح إذا وُجد مسار قوس قزح بين أي زوجين من الرؤوس. ويُسمى تلوين حواف الرسم البياني G بالألوان من 1 إلى t تلوينًا فاصليًا t إذا استُخدمت جميع الألوان، وكانت ألوان الحواف المتصلة بكل رأس من رؤوس G متميزة وتشكل فاصلًا من الأعداد الصحيحة.

التطبيقات

يمكن استخدام تلوين حواف الرسوم البيانية الكاملة لجدولة بطولة بنظام الدوري إلى أقل عدد ممكن من الجولات، بحيث يلعب كل زوج من المتنافسين ضد الآخر في إحدى الجولات. في هذا التطبيق، تمثل رؤوس الرسم البياني المتنافسين في البطولة، وتمثل الحواف المباريات، وتمثل ألوان الحواف الجولات التي تُلعب فيها المباريات. ^{[ 30 ]} يمكن أيضًا استخدام تقنيات تلوين مماثلة لجدولة مباريات رياضية أخرى لا تعتمد على نظام "الكل يلعب الكل"؛ على سبيل المثال، في دوري كرة القدم الأمريكية ، يتم تحديد أزواج الفرق التي ستلعب ضد بعضها البعض في عام معين، بناءً على سجلات الفرق من العام السابق، ثم يتم تطبيق خوارزمية تلوين الحواف على الرسم البياني المُشكّل من مجموعة الأزواج لتخصيص المباريات لعطلات نهاية الأسبوع التي تُقام فيها. ^{[ 31 ]} بالنسبة لهذا التطبيق، تشير نظرية فيزينغ إلى أنه بغض النظر عن مجموعة الأزواج المختارة (طالما لا يلعب أي فريق مع الآخر مرتين في نفس الموسم)، فمن الممكن دائمًا إيجاد جدول زمني يستخدم عطلة نهاية أسبوع واحدة على الأكثر أكثر من عدد المباريات لكل فريق.

تُعدّ جدولة الإنتاج في بيئة مفتوحة مسألةً تتعلق بجدولة عمليات الإنتاج ، حيث توجد مجموعة من المنتجات المراد تصنيعها، ولكل منتج مجموعة من المهام التي يجب تنفيذها عليه (بأي ترتيب)، ويجب تنفيذ كل مهمة على آلة محددة، مما يمنع تنفيذ أي مهمة أخرى تتطلب نفس الآلة في الوقت نفسه. إذا كانت جميع المهام متساوية في المدة، فيمكن صياغة هذه المسألة على أنها مسألة تلوين حواف رسم بياني ثنائي الأجزاء، حيث تمثل الرؤوس على أحد جانبي التقسيم الثنائي المنتجات المراد تصنيعها، وتمثل الرؤوس على الجانب الآخر آلات التصنيع، وتمثل الحواف المهام التي يجب تنفيذها، وتمثل الألوان الخطوات الزمنية التي يمكن خلالها تنفيذ كل مهمة. وبما أن تلوين حواف الرسم البياني الثنائي الأجزاء يمكن تنفيذه في وقت متعدد الحدود، فإن الأمر نفسه ينطبق على هذه الحالة المحدودة من جدولة الإنتاج في بيئة مفتوحة. ^{[ 32 ]}

درس غاندام، وداواندي، وبراكاش (2005) مشكلة جدولة الروابط لبروتوكولات اتصالات الشبكة متعددة الوصول بتقسيم الوقت على شبكات الاستشعار كنوع من تلوين الحواف. في هذه المشكلة، يجب اختيار فترات زمنية لحواف شبكة اتصالات لاسلكية بحيث تتمكن كل عقدة في الشبكة من التواصل مع كل عقدة مجاورة لها دون تداخل. استخدام تلوين قوي للحواف (باستخدام فترتين زمنيتين لكل لون حافة، واحدة لكل اتجاه) من شأنه حل المشكلة، ولكنه قد يتطلب عددًا أكبر من الفترات الزمنية اللازمة. بدلاً من ذلك، بحثوا عن تلوين للرسم البياني الموجه الناتج عن مضاعفة كل حافة غير موجهة في الشبكة، بحيث يكون لكل حافة موجهة $uv$ لون مختلف عن الحواف الخارجة من $v$ وعن حواف جيرانها . اقترحوا طريقة استدلالية لهذه المشكلة تعتمد على خوارزمية موزعة لتلوين $($ $Δ$ $+ 1) حافة$ $،$ بالإضافة إلى مرحلة معالجة لاحقة لإعادة جدولة الحواف التي قد تتداخل مع بعضها البعض.

في الاتصالات عبر الألياف الضوئية ، تُعرف مشكلة تلوين المسار بأنها مسألة تخصيص ألوان (ترددات ضوئية) لأزواج من العقد التي ترغب في التواصل فيما بينها، وللمسارات عبر شبكة اتصالات الألياف الضوئية لكل زوج، مع مراعاة شرط عدم استخدام مسارين يشتركان في جزء من الألياف نفس التردد. يُسمح للمسارات التي تمر عبر نفس مفتاح الاتصال ولكن ليس عبر أي جزء من الألياف باستخدام نفس التردد. عندما تُنظم شبكة الاتصالات على شكل شبكة نجمية ، مع مفتاح مركزي واحد متصل بألياف منفصلة بكل عقدة، يمكن نمذجة مشكلة تلوين المسار تمامًا كمشكلة تلوين حواف رسم بياني أو رسم بياني متعدد، حيث تُشكل العقد المتصلة رؤوس الرسم البياني، وتُشكل أزواج العقد التي ترغب في التواصل حواف الرسم البياني، وتُشكل الترددات التي يمكن استخدامها لكل زوج ألوان مشكلة تلوين الحواف. بالنسبة لشبكات الاتصالات ذات بنية شجرية أكثر عمومية، يمكن دمج حلول تلوين المسار المحلي لشبكات النجوم المحددة بواسطة كل مفتاح في الشبكة لتشكيل حل عالمي واحد. ^{[ 33 ]}

المشكلات المفتوحة

أدرج جنسن وتوفت (1995) 23 مشكلة مفتوحة تتعلق بتلوين الحواف. وتشمل هذه المشاكل ما يلي:

الفرضية التي طرحها غولدبرغ (1973) هي أن المؤشر اللوني والمؤشر الكسري يقعان ضمن واحد من بعضهما البعض، مما يسمح بتقريب المؤشر اللوني ضمن لون واحد في وقت متعدد الحدود.
توجد عدة فرضيات لجاكوبسن وآخرين حول بنية الرسوم البيانية الحرجة لتلوين الحواف، وهي رسوم بيانية من الفئة 2 بحيث يكون لأي رسم بياني فرعي إما درجة قصوى أصغر أو يكون من الفئة 1. افترض جاكوبسن في البداية أن جميع الرسوم البيانية الحرجة لها عدد فردي من الرؤوس، ولكن تم دحض هذا الافتراض لاحقًا. ولا تزال هناك عدة فرضيات أخرى مفتوحة، إما تُضعف هذه الفرضية أو تحدد عدد رؤوس الرسوم البيانية الحرجة والرسوم البيانية المتعددة الحرجة.
مشكلة فيزينغ المتمثلة في تصنيف الدرجات القصوى الممكنة للرسوم البيانية المستوية من الفئة 2.
الفرضية الفرعية المفرطة لـ AJW Hilton، التي تنص على أن الرسوم البيانية ذات الدرجة $n /3$ على الأقل إما أن تكون من الفئة 1 أو تحتوي على رسم بياني فرعي بنفس الدرجة $Δ$ مثل الرسم البياني الأصلي، وبعدد فردي $k$ من الرؤوس، بحيث يكون عدد الحواف في الرسم البياني الفرعي أكبر من $Δ (k - 1)/2$ ، وفرضية مماثلة لهيربرت غروتزش وبول سيمور فيما يتعلق بالرسوم البيانية المستوية بدلاً من الرسوم البيانية ذات الدرجة العالية.
فرضية أماندا تشيتويند وأنتوني هيلتون (ربما تعود إلى أعمال غابرييل أندرو ديراك ) مفادها أن الرسوم البيانية المنتظمة التي تحتوي على عدد زوجي $n$ من الرؤوس وبدرجة لا تقل عن $n /2$ هي من الفئة 1.
فرضية كلود بيرج ودي آر فولكرسون مفادها أن الرسوم البيانية المتعددة المنتظمة من الدرجة 6 التي تشكلت عن طريق مضاعفة كل حافة من الرسم البياني البسيط المنتظم من الدرجة 3 بدون جسر يمكن تلوين حوافها بستة ألوان.
فرضية فيوريني وويلسون مفادها أن كل رسم بياني مستوٍ خالٍ من المثلثات ، بخلاف الرسم البياني المخلبي K _1,3 ، ليس قابلاً للتلوين بثلاثة ألوان بشكل فريد .
فرضيةٌ طُرحت عام ٢٠١٢ تنص على أنه إذا كان $G$ رسمًا بيانيًا مستويًا متعددًا منتظمًا من الدرجة $d ، فإن$ $G$ يكون قابلًا للتلوين $بـ d$ من الحواف إذا وفقط إذا كان $G متصلًا$ $بـ d من$ الحواف بشكل فردي. تُعد هذه الفرضية تعميمًا لنظرية الألوان الأربعة ، التي تظهر عند $d$ = 3. وقد أثبتت ماريا تشودنوفسكي وكاثرين إدواردز وبول سيمور أن الرسم البياني المستوي المتعدد المنتظم من الدرجة 8 له عدد تلوين حواف يساوي 8. ^{[ ٣٤ ]}

ملحوظات

^ سويفر (2008) ، المشكلة 16.4، ص. 133.
↑ Soifer (2008) ، المسألة 16.5، ص 133. إن حقيقة أن هناك حاجة إما إلى $n$ أو $(n - 1)$ لونًا هي مثال على نظرية فيزينغ .
↑ بيغز (1972) ؛ ميريديث ولويد (1973) ؛ بيغز (1979) .
1 2 Soifer (2008) ، ص. 134.
↑ كونيغ (1916)
↑ إردوس وويلسون (1977) .
↑ هولير (1981) .
↑ ساندرز وتشاو (2001) .
^ تيت (1880) ؛ ابيل وهاكين (1976) .
↑ سويفر (2008) ، ص 136.
^ بار نوي ومتواني وناعور (1992) .
^ بهماني وميهتا ومتواني (2010) .
↑ غولدبرغ (1973) ؛ أندرسن (1977) ؛ سيمور (1979) .
^ تشين ويو وزانغ (2011) .
↑ إبستين (2013) .
↑ شوينك (1989) .
↑ بوساك (1972) .
^ أكياما، إكسو وهراري (1980) ؛ حبيب وبيروش (1982) ; هوراك ونيبل (1982) .
↑ ناش-ويليامز (1964) .
↑ جابو وويسترمان (1992) .
^ بوساك ونيشتريل (1976) .
↑ فوكيه وجوليفيه (1983) ؛ مهديان (2002) ؛ فريز، كريفيلفيتش وسوداكوف (2005) ؛ كرانستون (2006) .
↑ باريت وآخرون (2006) .
^ ألون وسوداكوف وزاكس (2001) ؛ موثو، نارايانان وسوبرامانيان (2007) .
^ فيامشيك (1978) ؛ ألون وسوداكوف وزاكس (2001)
↑ جيوتيس وآخرون (2015) .
^ ألون وسوداكوف وزاكس (2001) .
↑ كاي وآخرون (2014) .
↑ إبستين (2010) .
^ بيرك ودي ويرا وكينغستون (2004) .
↑ Skiena (2008) .
↑ ويليامسون وآخرون (1997) .
↑ إيرليباخ وجانسن (2001) .
↑ تشودنوفسكي، إدواردز وسيمور (2015) .

مراجع

أكياما، جين؛ إكسو، جيفري؛ هاراري، فرانك (1980)، "التغطية والتعبئة في الرسوم البيانية. الجزء الثالث: الثوابت الدورية وغير الدورية"، مجلة الرياضيات السلوفاكية ، 30 (4): 405-417 ، MR 0595302 .
ألون، نوغا (2003)، "خوارزمية بسيطة لتلوين حواف الرسوم البيانية المتعددة ثنائية الأجزاء"، رسائل معالجة المعلومات ، 85 (6): 301-302 ، doi : 10.1016/S0020-0190(02)00446-5 ، MR 1956451 ، S2CID 34965604 .
ألون، نوغا ؛ سوداكوف، بيني؛ زاكس، أيال (2001)، "تلوين حواف الرسوم البيانية غير الدورية"، مجلة نظرية الرسوم البيانية ، 37 (3): 157-167 ، doi : 10.1002/jgt.1010 ، MR 1837021 .
أندرسن، لارس دوفلينغ (1977)، "حول تلوين حواف الرسوم البيانية"، مجلة الرياضيات الإسكندنافية ، 40 (2): 161-175 ، doi : 10.7146/math.scand.a-11685 ، MR 0465922 كما ورد في تشين، يو وزانغ (2011) .
أبيل، ك .؛ هاكن، و. (1976)، "كل خريطة مستوية قابلة للتلوين بأربعة ألوان"، نشرة الجمعية الرياضية الأمريكية ، 82 (5): 711-712 ، doi : 10.1090/S0002-9904-1976-14122-5 ، MR 0424602 .
بهماني، بهمان؛ ميهتا، أرانياك؛ موتاني، راجيف (2010)، "خوارزمية تلوين حواف الرسوم البيانية عبر الإنترنت تنافسية بنسبة 1.43 في نموذج الوصول بترتيب عشوائي"، وقائع الندوة السنوية الحادية والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA '10) ، جمعية الرياضيات الصناعية والتطبيقية، الصفحات 31-39 ، ISBN 9780898716986.
بار-نوي، أموتز؛ موتاني، راجيف ؛ ناور، جوزيف (1992)، "الخوارزمية الجشعة هي الأمثل لتلوين الحواف عبر الإنترنت"، رسائل معالجة المعلومات ، 44 (5): 251-253 ، doi : 10.1016/0020-0190(92)90209-E.
باريت، سي إل؛ إسترات، جي؛ كومار، في إس إيه؛ ماراثي، إم في؛ ثيت، إس؛ ثولاسيداسان، إس (2006)، "تلوين الحواف القوي لتخصيص القنوات في شبكات الراديو اللاسلكية"، وقائع المؤتمر الدولي السنوي الرابع لمعهد مهندسي الكهرباء والإلكترونيات حول ورش عمل الحوسبة والاتصالات المنتشرة (PerCom Workshops 2006) ، ص 106، doi : 10.1109/PERCOMW.2006.129 ، ISBN 0-7695-2520-2، S2CID 5797236 .
بيغز، نورمان (1972)، غاي، ريتشارد ك . (محرر)، "مسألة تلوين الحواف"، مسائل بحثية، المجلة الرياضية الأمريكية الشهرية ، 79 (9): 1018-1020 ، doi : 10.2307/2318076 ، JSTOR 2318076 .
بيغز، نورمان (1979)، "بعض نظريات الرسم البياني الغريبة"، المؤتمر الدولي الثاني للرياضيات التوافقية، حوليات أكاديمية نيويورك للعلوم ، 319 (1): 71-81 ، Bibcode : 1979NYASA.319...71B ، doi : 10.1111/j.1749-6632.1979.tb32775.x ، S2CID 84995087 .
بيوركلوند، أندرياس؛ هوسفيلدت، ثور. Koivisto، Mikko (2009)، “تعيين التقسيم عبر الاستبعاد والإدراج” (PDF) ، مجلة SIAM حول الحوسبة ، 39 (2): 546–563 ، دوى : 10.1137 / 070683933 ، السيد 2529771 .
بوساك، يوراي (1972)، "المؤشر اللوني للرسوم البيانية المحدودة وغير المحدودة"، المجلة الرياضية التشيكوسلوفاكية ، 22 (97): 272-290 ، doi : 10.21136/CMJ.1972.101098 ، MR 0309777 .
بوساك، يوراج؛ Nešetřil، Jaroslav (1976)، “التلوين الكامل والزائف للرسم البياني”، Matematicky Časopis Slovenskej Akadémie Vied ، 26 (3): 171–184 ، MR 0439672 .
كاي، إكس إس؛ بيرناو، جي؛ ريد، بي إيه ؛ واتس، إيه بي (2014)، "تلوين حواف الرسوم البيانية غير الدورية ذات المحيط الكبير"، الهياكل والخوارزميات العشوائية ، 50 (4): 511-533 ، arXiv : 1411.3047 ، doi : 10.1002/rsa.20695 ، S2CID 7727097 .
بيرك، إي.؛ دي ويرا، د.؛ كينغستون، ج. (2004)، "5.6.5 جدولة المباريات الرياضية" ، في ج. ل. غروس؛ يلين، ج. (محرران)، دليل نظرية الرسم البياني ، مطبعة سي آر سي، ص 462، رقم ISBN 978-1-58488-090-5.
تشين، غوانتاو؛ يو، شينغشينغ؛ زانغ، وينان (2011)، "تقريب المؤشر اللوني للرسوم البيانية المتعددة"، مجلة التحسين التوافقي ، 21 (2): 219-246 ، doi : 10.1007/s10878-009-9232-y ، MR 2770056 ، S2CID 169162 .
تشودنوفسكي، ماريا ؛ إدواردز، كاثرين؛ سيمور، بول (نوفمبر 2015)، "تلوين حواف الرسوم البيانية المستوية المنتظمة ثمانية"، مجلة نظرية التوافيق ، السلسلة ب، 115 : 303-338 ، arXiv : 1209.1176 ، doi : 10.1016/j.jctb.2015.05.002.
كول، ريتشارد ؛ هوبكروفت، جون (1982)، "حول تلوين حواف الرسوم البيانية ثنائية الأجزاء"، مجلة SIAM للحوسبة ، 11 (3): 540-546 ، doi : 10.1137/0211043 ، hdl : 1813/6283 ، MR 0664720 .
كول، ريتشارد؛ كواليك، لوكاس (2008)، "خوارزميات جديدة ذات زمن خطي لتلوين حواف الرسوم البيانية المستوية"، Algorithmica ، 50 (3): 351-368 ، doi : 10.1007/s00453-007-9044-3 ، MR 2366985 ، S2CID 7692895 .
كول، ريتشارد؛ أوست، كيرستين؛ شيرا، ستيفان (2001)، "تلوين حواف الرسوم البيانية المتعددة الأجزاء الثنائية في زمن $O(E log D)$ "، كومبيناتوريكا ، 21 (1): 5-12 ، doi : 10.1007/s004930170002 ، MR 1805711 ، S2CID 522145 .
كرانستون، دانيال و. (2006)، "تلوين حواف قوي للرسوم البيانية ذات الدرجة القصوى 4 باستخدام 22 لونًا"، الرياضيات المتقطعة ، 306 (21): 2772-2778 ، arXiv : math/0601623 ، Bibcode : 2006math......1623C ، doi : 10.1016/j.disc.2006.03.053 ، MR 2264374 ، S2CID 1097275 .
إبستين، ديفيد (2013)، "تعقيد رسم المخططات المتعامدة ثلاثية الأبعاد بدون انحناء"، مجلة خوارزميات وتطبيقات المخططات ، 17 (1): 35-55 ، arXiv : 0709.4087 ، doi : 10.7155/jgaa.00283 ، S2CID 2716392 .
إبستين، ديفيد (2010)، "التسميات المنتظمة والبنى الهندسية"، وقائع المؤتمر الكندي الثاني والعشرين للهندسة الحاسوبية (CCCG 2010) (ملف PDF) ، جامعة مانيتوبا، arXiv : 1007.0221 ، Bibcode : 2010arXiv1007.0221E.
إيردوس، بول ؛ ويلسون، روبن ج. (1977)، "ملاحظة حول المؤشر اللوني لجميع الرسوم البيانية تقريبًا" (ملف PDF) ، مجلة نظرية التوافيق ، السلسلة ب، 23 ( 2-3 ): 255-257 ، doi : 10.1016/0095-8956(77)90039-9.
إيرليباخ، توماس؛ جانسن، كلاوس (2001)، "تعقيد تلوين المسار وجدولة المكالمات"، علوم الحاسوب النظرية ، 255 ( 1-2 ): 33-50 ، doi : 10.1016/S0304-3975(99)00152-8 ، hdl : 2381/18057 ، MR 1819065 .
فيربر، آصف؛ جاين، فيشيش (سبتمبر 2020)، "تحليلات أحادية للرسوم البيانية شبه العشوائية"، الهياكل والخوارزميات العشوائية ، 57 (2): 259-278 ، arXiv : 1803.10361 ، doi : 10.1002/rsa.20927 ، S2CID 4680445 .
فيامتشيك، ج. ( 1978)، "الفئة اللونية غير الدورية للرسم البياني"، الرياضيات السلوفاكية ، 28 : 139-145.
فيوريني، س.؛ ويلسون، روبن جيمس (1977)، تلوين حواف الرسوم البيانية ، مذكرات بحثية في الرياضيات، المجلد 16، لندن: بيتمان، ISBN 0-273-01129-4، MR 0543798 .
فولكمان، جون ؛ فولكرسون، د. ر. (1969)، "تلوين الحواف في الرسوم البيانية ثنائية الأجزاء"، الرياضيات التوافقية وتطبيقاتها (وقائع المؤتمر، جامعة نورث كارولينا، تشابل هيل، نورث كارولينا، 1967) ، تشابل هيل، نورث كارولينا: مطبعة جامعة نورث كارولينا، الصفحات 561-577 ، MR 0262112 .
فوكيه، جيه.-إل.؛ جوليفيه، جيه.-إل. (1983)، "تلوين الحواف القوي للرسوم البيانية وتطبيقاته على المضلعات متعددة الأضلاع من النوع $k$ "، آرس كومبيناتوريا ، 16 (أ): 141-150 ، MR 0737086 .
فريز، آلان م .؛ كريفيليتش، مايكل ؛ سوداكوف، بيني (2005)، "المؤشر اللوني القوي للرسوم البيانية العشوائية" (ملف PDF) ، مجلة SIAM للرياضيات المتقطعة ، 19 (3): 719-727 (إلكتروني)، doi : 10.1137/S0895480104445757 ، MR 2191290 .
جابو، هارولد ن. (1976)، "استخدام تقسيمات أويلر لتلوين حواف الرسوم البيانية المتعددة الأجزاء ثنائية الأجزاء"، المجلة الدولية لعلوم الحاسوب والمعلومات ، 5 (4): 345-355 ، doi : 10.1007/BF00998632 ، MR 0422081 ، S2CID 36331285 .
جابو، هارولد ن .؛ نيشيزيكي، تاكاو ؛ كاريف، أوديد؛ ليفين، دانيال؛ تيرادا، أوسامو (1985)، خوارزميات لتلوين حواف الرسوم البيانية ، تقرير فني رقم TRECIS-8501، جامعة توهوكو.
جابو، هارولد ن .؛ ويسترمان، هربرت هـ. (1992)، "الغابات، والإطارات، والألعاب: خوارزميات لمجاميع الماترويد وتطبيقاتها"، Algorithmica ، 7 ( 5-6 ): 465-497 ، doi : 10.1007/BF01758774 ، MR 1154585 ، S2CID 40358357 .
جالفين، ف. (1995)، "مؤشر التلوين القائم على القوائم للرسم البياني المتعدد ثنائي الأجزاء"، مجلة نظرية التوافيق ، السلسلة ب، 63 (1): 153-158 ، doi : 10.1006/jctb.1995.1011.
غاندام، س.؛ داواندي، م.؛ براكاش، ر. (2005)، "جدولة الروابط في شبكات الاستشعار: إعادة النظر في تلوين الحواف الموزعة"، وقائع المؤتمر الدولي الرابع والعشرين لشبكات الاستشعار والمعلومات (INFOCOM )، المجلد 4، الصفحات 2492-2501 ، doi : 10.1109/INFCOM.2005.1498534 ، ISBN 0-7803-8968-9، S2CID 8085139 .
جيوتيس، آي.؛ كيروسيس، إل.؛ بساروميلجكوس، كي آي؛ ثيليكوس، دي إم (2015)، "حول خوارزمية لوفاس المحلية وتلوين الحواف غير الدوري"، وقائع ورشة العمل الثانية عشرة حول الخوارزميات التحليلية والتوافقية (ANALCO) ، ص 16، doi : 10.1137/1.9781611973761.2 ، ISBN 978-1-61197-376-1.
غولدبيرغ، إم كيه (1973)، "الرسوم البيانية المتعددة ذات المؤشر اللوني شبه الأقصى"، التحليل المنفصل (23): 3-7 ، 72، MR 0354429 كما ورد في تشين، يو وزانغ (2011) .
حبيب، م.؛ بيروش، ب. (1982)، "بعض المشاكل المتعلقة بالتشعب الخطي"، الرياضيات المتقطعة ، 41 (2): 219-220 ، doi : 10.1016/0012-365X(82)90209-6 ، MR 0676882 .
هولير، إيان (1981)، "اكتمال NP لتلوين الحواف"، مجلة SIAM للحوسبة ، 10 (4): 718-720 ، doi : 10.1137/0210055 ، S2CID 13131049 .
هوراك، بيتر؛ Niepel، Ľudovít (1982)، “دليل قصير على نظرية الشجرة الخطية للرسوم البيانية المكعبة”، Acta Mathematica Universitatis Comenianae ، 40/41: 275–277 ، MR 0686983 .
جنسن، تومي ر.؛ توفت، بيارن (1995)، مسائل تلوين الرسوم البيانية ، نيويورك: وايلي-إنترساينس، ISBN 0-471-02865-7.
كارلوف، هوارد جيه؛ شمويز، ديفيد بي (1987)، "خوارزميات متوازية فعالة لمسائل تلوين الحواف"، مجلة الخوارزميات ، 8 (1): 39-52 ، doi : 10.1016/0196-6774(87)90026-5 ، MR 0875324 .
Kőnig، D. (1916)، “Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre” ، مجلة الرياضيات ، 77 (4): 453–465 ، دوى : 10.1007 / BF01456961 ، hdl : 10338.dmlcz / 127635 ، S2CID 121097364 ، أرشفة من النسخة الأصلية بتاريخ 19-01-2015 ، استرجاعها 30-09-2013 .
كواليك، لوكاس (2009)، "تحسين تلوين الحواف بثلاثة ألوان"، علوم الحاسوب النظرية ، 410 ( 38-40 ): 3733-3742 ، doi : 10.1016/j.tcs.2009.05.005 ، MR 2553326 .
مهديان، محمد (2002)، "حول التعقيد الحسابي لتلوين الحواف القوي"، الرياضيات التطبيقية المنفصلة ، 118 (3): 239-248 ، doi : 10.1016/S0166-218X(01)00237-2 ، MR 1892971 .
ميريديث، جاي إتش جيه؛ لويد، إي. كيث (1973)، "لاعبو كرة القدم في كروم"، مجلة نظرية التوافيق ، السلسلة ب، 15 (2): 161-166 ، doi : 10.1016/0095-8956(73)90016-6.
ميسرا، ج.؛ غريس، ديفيد (1992)، "برهان بنائي لنظرية فيزينغ"، رسائل معالجة المعلومات ، 41 (3): 131-133 ، doi : 10.1016/0020-0190(92)90041-S.
موثو، راهول؛ نارايانان، ن.؛ سوبرامانيان، سي آر (2007)، "حدود محسّنة لتلوين الحواف غير الدورية"، الرياضيات المتقطعة ، 307 (23): 3063-3069 ، doi : 10.1016/j.disc.2007.03.006 ، MR 2371078 .
ناش-ويليامز، سي. سانت جيه إيه (1964)، "تحليل الرسوم البيانية المحدودة إلى غابات"، مجلة جمعية لندن الرياضية ، السلسلة الثانية، 39 : 12، doi : 10.1112/jlms/s1-39.1.12 ، MR 0161333
نيمهاوزر، جورج ل .؛ بارك، سونغسو (1991)، "نهج متعدد السطوح لتلوين الحواف"، رسائل بحوث العمليات ، 10 (6): 315-322 ، doi : 10.1016/0167-6377(91)90003-8 ، MR 1128970 .
ريختر، ديفيد أ. (2011)، "كيفية رسم رسم بياني قابل للتلوين باستخدام ألوان تايت"، في براندس، أولريك ؛ كورنيلسن، سابين (محرران)، وقائع الندوة الدولية الثامنة عشرة حول رسم الرسوم البيانية (GD 2010) ، سلسلة محاضرات في علوم الحاسوب، المجلد 6502، سبرينغر-فيرلاغ، الصفحات 353-364 ، doi : 10.1007/978-3-642-18469-7_32 ، ISBN 978-3-642-18468-0.
ساندرز، دانيال ب .؛ تشاو، يو (2001)، "الرسوم البيانية المستوية ذات الدرجة القصوى سبعة هي من الفئة الأولى"، مجلة نظرية التوافيق ، السلسلة ب، 83 (2): 201-212 ، doi : 10.1006/jctb.2001.2047.
سيمور، بي دي (1979)، "حول التلوين المتعدد للرسوم البيانية المكعبة، وتخمينات فولكرسون وتوت"، وقائع الجمعية الرياضية بلندن ، السلسلة الثالثة، 38 (3): 423-460 ، doi : 10.1112/plms/s3-38.3.423 ، MR 0532981 .
شوينك، ألين ج. (1989)، "تعداد دورات هاميلتون في بعض رسوم بيترسن المعممة"، مجلة نظرية التوافيق ، السلسلة ب، 47 (1): 53-59 ، doi : 10.1016/0095-8956(89)90064-6 ، MR 1007713 .
شانون، كلود إي. (1949)، "نظرية حول تلوين خطوط الشبكة"، مجلة الرياضيات والفيزياء ، 28 ( 1-4 ): 148-151 ، doi : 10.1002/sapm1949281148 ، hdl : 10338.dmlcz/101098 ، MR 0030203 .
سكينا، ستيفن س. (2008)، "16.8 تلوين الحواف"، دليل تصميم الخوارزميات ( الطبعة الثانية)، سبرينغر-فيرلاغ، ص 548-550 ، doi : 10.1007/978-1-84800-070-4_16 ، ISBN 978-1-84800-069-8انظر أيضًا إلى موقع الويب الخاص بهذا القسم من الكتاب في مستودع خوارزميات ستوني بروك.
سوفر، ألكسندر (2008)، كتاب التلوين الرياضي ، سبرينغر-فيرلاغ، رقم ISBN 978-0-387-74640-1.
تايت، بي جي (1880)، "ملاحظات حول تلوين الخرائط"، وقائع الجمعية الملكية في إدنبرة ، 10 : 729، doi : 10.1017/S0370164600044643.
تراهتمان، أفراهام ن. (2009)، "مسألة تلوين الطرق"، مجلة إسرائيل للرياضيات ، 172 (1): 51-60 ، arXiv : 0709.0099 ، doi : 10.1007/s11856-009-0062-5 ، S2CID 515742 .
فيزينغ، في جي (1964)، "حول تقدير الفئة اللونية للرسم البياني من الرتبة p "، التحليل المنفصل ، 3 : 25-30 ، MR 0180505 .
فيزينغ، في جي ( 1965)، "الرسوم البيانية الحرجة ذات الفئة اللونية المعطاة"، ميثودي ديسكريت. أناليز. ، 5 : 9-17(باللغة الروسية.)
الأماكن القريبة : هول، لوس أنجلوس؛ هوجيفين، JA؛ هوركينز، كاج. الأماكن القريبة : سيفاستجانوف، SV؛ Shmoys، DB (1997)، “جداول المتجر القصيرة”، بحوث العمليات ، 45 (2): 288-294 ، دوى : 10.1287/opre.45.2.288 ، JSTOR 171745 ، MR 1644998 .
تشو، شياو؛ ناكانو، شين-إيتشي؛ نيشيزيكي، تاكاو (1996)، "تلوين حواف الأشجار الجزئية من الرتبة $k$ "، مجلة الخوارزميات ، 21 (3): 598-617 ، doi : 10.1006/jagm.1996.0061 ، MR 1417666 .

[1] سويفر (2008) ، المشكلة 16.4، ص. 133.

[2] Soifer (2008) ، المسألة 16.5، ص 133. إن حقيقة أن هناك حاجة إما إلى $n$ أو $(n - 1)$ لونًا هي مثال على نظرية فيزينغ .

[3] بيغز (1972) ؛ ميريديث ولويد (1973) ؛ بيغز (1979) .

[s134-4] 1 2 Soifer (2008) ، ص. 134.

[5] كونيغ (1916)

[6] إردوس وويلسون (1977) .

[7] هولير (1981) .

[8] ساندرز وتشاو (2001) .

[9] تيت (1880) ؛ ابيل وهاكين (1976) .

[10] سويفر (2008) ، ص 136.

[11] بار نوي ومتواني وناعور (1992) .

[12] بهماني وميهتا ومتواني (2010) .

[13] غولدبرغ (1973) ؛ أندرسن (1977) ؛ سيمور (1979) .

[14] تشين ويو وزانغ (2011) .

[15] إبستين (2013) .

[16] شوينك (1989) .

[17] بوساك (1972) .

[18] أكياما، إكسو وهراري (1980) ؛ حبيب وبيروش (1982) ; هوراك ونيبل (1982) .

[19] ناش-ويليامز (1964) .

[20] جابو وويسترمان (1992) .

[FOOTNOTEBosákNešetřil1976-21] بوساك ونيشتريل (1976) .

[22] فوكيه وجوليفيه (1983) ؛ مهديان (2002) ؛ فريز، كريفيلفيتش وسوداكوف (2005) ؛ كرانستون (2006) .

[FOOTNOTEBarrettIstrateKumarMarathe2006-23] باريت وآخرون (2006) .

[24] ألون وسوداكوف وزاكس (2001) ؛ موثو، نارايانان وسوبرامانيان (2007) .

[25] فيامشيك (1978) ؛ ألون وسوداكوف وزاكس (2001)

[FOOTNOTEGiotisKirousisPsaromiligkosThilikos2015-26] جيوتيس وآخرون (2015) .

[FOOTNOTEAlonSudakovZaks2001-27] ألون وسوداكوف وزاكس (2001) .

[FOOTNOTECaiPerarnauReedWatts2014-28] كاي وآخرون (2014) .

[29] إبستين (2010) .

[30] بيرك ودي ويرا وكينغستون (2004) .

[31] Skiena (2008) .

[32] ويليامسون وآخرون (1997) .

[33] إيرليباخ وجانسن (2001) .

[FOOTNOTEChudnovskyEdwardsSeymour2015-34] تشودنوفسكي، إدواردز وسيمور (2015) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[

[ 8 ]

[

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

25

26 ] تصبح

27 ]

28

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ ٣٤ ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗