تلوين كامل

مشكلة لم تُحل في الرياضيات

تخمين:${\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

المزيد من المسائل غير المحلولة في الرياضيات

في نظرية الرسوم البيانية ، يُعد التلوين الكلي نوعًا من أنواع تلوين رؤوس وحواف الرسم البياني. عند استخدامه دون أي تحديد، يُفترض دائمًا أن التلوين الكلي صحيح بمعنى أنه لا توجد حواف متجاورة، ولا رؤوس متجاورة، ولا حافة ورأس طرفي مُلوّنان بنفس اللون. يُعرف العدد اللوني الكلي χ ″( G ) للرسم البياني G بأنه أقل عدد من الألوان اللازمة لأي تلوين كلي للرسم البياني G.

الرسم البياني الكلي T = T ( G ) للرسم البياني G هو رسم بياني بحيث (أ) تتطابق مجموعة رؤوس T مع رؤوس وحواف G ، و(ب) يكون رأسان متجاورين في T إذا وفقط إذا كانت عناصرهما المتناظرة إما متجاورة أو متصلة في G. عندئذٍ، يصبح التلوين الكلي لـ G تلوينًا (صحيحًا) لرؤوس T ( G ) . التلوين الكلي هو تقسيم رؤوس وحواف الرسم البياني إلى مجموعات مستقلة كليًا .

بعض المتباينات لـ χ ″( G ) :

1. ${\displaystyle \chi ''(G)\geq \Delta (G)+1.}$
2. ${\displaystyle \chi ''(G)\leq \Delta (G)+10^{26}.}$ (مولوي، ريد 1998)
3. ${\displaystyle \chi ''(G)\leq \Delta (G)+8\ln ^{8}(\Delta (G))}$لـ Δ ( G ) كبيرة بما فيه الكفاية . (هيند، مولوي، ريد 1998)
4. ${\displaystyle \chi ''(G)\leq \operatorname {ch} '(G)+2.}$

هنا Δ( G ) هي الدرجة القصوى ؛ و ch′( G ) ، قابلية اختيار الحافة .

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

يُعدّ حساب الحد الأعلى للدرجة القصوى باستخدام التلوين الكلي مسألةً معقدةً استعصت على علماء الرياضيات لخمسين عامًا. ويُمكن إيجاد حد أدنى بسيط لـ χ ″( G ) وهو Δ( G ) + 1. بعض الرسوم البيانية، مثل الدورات ذات الطول${\displaystyle n\not \equiv 0{\bmod {3}}}$وتحتاج الرسوم البيانية الثنائية الكاملة من الشكل K _n,n إلى Δ( G ) + 2 لونًا، ولكن لم يُعثر على أي رسم بياني يتطلب ألوانًا أكثر. وهذا يقود إلى التكهن بأن كل رسم بياني يحتاج إما إلى Δ( G ) + 1 أو Δ( G ) + 2 لونًا، وليس أكثر من ذلك أبدًا.

تخمين التلوين الكلي ( بهزاد ، فيزينغ).${\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

يبدو أن مصطلح "التلوين الكلي" وفرضية التلوين الكلي قد طُرحا بشكل مستقل من قِبل بهزاد وفيزينغ في مناسبات عديدة بين عامي 1964 و1968 (انظر جنسن وتوفت). من المعروف أن هذه الفرضية صحيحة لبعض فئات الرسوم البيانية المهمة، مثل جميع الرسوم البيانية ثنائية الأجزاء ومعظم الرسوم البيانية المستوية باستثناء تلك التي تبلغ درجتها القصوى 6. يمكن استكمال حالة الرسوم البيانية المستوية إذا كانت فرضية فيزينغ للرسوم البيانية المستوية صحيحة. كذلك، إذا كانت فرضية تلوين القوائم صحيحة، فإن${\displaystyle \chi ''(G)\leq \Delta (G)+3.}$

تم الحصول على نتائج تتعلق بالتلوين الكلي. على سبيل المثال، أثبت كيلاكوس وريد (1993) أن العدد اللوني الجزئي للرسم البياني الكلي للرسم البياني G هو على الأكثر Δ( G ) + 2 .

• هيند، هيو؛ مولوي، مايكل؛ ريد، بروس (1998). "التلوين الكلي باستخدام Δ + متعدد (لوغاريتم Δ) لونًا". مجلة SIAM للحوسبة . 28 (3): 816-821 . doi : 10.1137/S0097539795294578 .
• جنسن، تومي ر.؛ توفت، بيارن (1995). مسائل تلوين الرسوم البيانية . نيويورك: وايلي-إنترساينس. ISBN 0-471-02865-7.
• كيلاكوس، كيرياكوس؛ ريد، بروس (1993). "تلوين الرسوم البيانية الكلية جزئيًا". كومبيناتوريكا . 13 (4): 435-440 . doi : 10.1007/BF01303515 . S2CID 31163141 . 
• مولوي، مايكل؛ ريد، بروس (1998). "حد أقصى للعدد اللوني الكلي". كومبيناتوريكا . 18 (2): 241-280 . doi : 10.1007/PL00009820 . hdl : 1807/9465 . S2CID 9600550 .