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

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