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

عند استخدام مصطلح " تلوين الرسم البياني" دون أي تحديد، فإنه يشير في الغالب إلى تلوين الرؤوس الصحيح ، أي ترقيم رؤوس الرسم البياني بألوان لا تتشابه في اللون بين أي رأسين يشتركان في نفس الحافة . ​​وبما أن الرأس الذي يحتوي على حلقة (أي اتصال مباشر مع نفسه) لا يمكن تلوينه بشكل صحيح، فمن المفهوم أن الرسوم البيانية في هذا السياق تكون خالية من الحلقات.

يعود استخدام الألوان لتسمية الرؤوس إلى تلوين الخرائط. ولا تُستخدم تسميات مثل الأحمر والأزرق إلا عندما يكون عدد الألوان قليلاً، ومن المفهوم عادةً أن التسميات تُستمد من الأعداد الصحيحة { 1 ، 2، 3، ...} .

يُطلق على التلوين الذي يستخدم k لونًا على الأكثر اسم التلوين k- الصحيح. يُسمى أصغر عدد من الألوان اللازمة لتلوين الرسم البياني G بالعدد اللوني ، ويُرمز له غالبًا بـ χ( G ) . ^{[ 5 ]} يُستخدم أحيانًا γ( G ) ، لأن χ( G ) يُستخدم أيضًا للدلالة على خاصية أويلر للرسم البياني. ^{[ 6 ]} يُسمى الرسم البياني الذي يمكن تلوينه k- الصحيح قابلًا للتلوين k- ، ويكون k- لونيًا إذا كان عدده اللوني يساوي k بالضبط . تُسمى مجموعة فرعية من الرؤوس المُخصصة لنفس اللون فئة لونية ؛ تُشكل كل فئة من هذه الفئات مجموعة مستقلة . بالتالي، فإن التلوين k- الصحيح هو نفسه تقسيم مجموعة الرؤوس إلى k مجموعة مستقلة، ولمصطلحي k- الجزئي وقابل للتلوين k- الصحيح نفس المعنى.

تُحسب دالة التلوين عدد الطرق الممكنة لتلوين رسم بياني باستخدام عدد معين من الألوان. على سبيل المثال، باستخدام ثلاثة ألوان، يمكن تلوين الرسم البياني في الصورة المجاورة بـ 12 طريقة. باستخدام لونين فقط، لا يمكن تلوينه على الإطلاق. باستخدام أربعة ألوان، يمكن تلوينه بـ 24 + 4 × 12 = 72 طريقة: باستخدام الألوان الأربعة جميعها، يوجد 4! = 24 تلوينًا صحيحًا ( كل تخصيص لأربعة ألوان لأي رسم بياني ذي 4 رؤوس هو تلوين صحيح)؛ ولكل اختيار لثلاثة من الألوان الأربعة، يوجد 12 تلوينًا صحيحًا بثلاثة ألوان. لذا، بالنسبة للرسم البياني في المثال، سيبدأ جدول عدد التلوينات الصحيحة على النحو التالي:

الدالة اللونية متعددة الحدود هي دالة P ( G , t ) تحسب عدد مرات تلوين G بـ t لونًا . وكما يشير الاسم، بالنسبة لرسم بياني G معين، فإن الدالة هي بالفعل متعددة حدود في t . في الرسم البياني الموضح في المثال، P ( G , t ) = t ( t - 1) ^{/ 2} ( t - 2) ، وبالفعل P ( G , 4) = 72 .

تتضمن متعددة الحدود اللونية معلومات أكثر عن قابلية تلوين G مقارنةً بالعدد اللوني. في الواقع، χ هو أصغر عدد صحيح موجب ليس صفرًا لمتعددة الحدود اللونية χ( G ) = min { k  : P ( G , k ) > 0 } .

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

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

بالنسبة للرسم البياني ذي التضمين القوي على سطح ما، فإن تلوين الوجه هو ثنائي مشكلة تلوين الرؤوس.

بالنسبة للرسم البياني G ذي التضمين القوي على سطح قابل للتوجيه، اكتشف ويليام تي. توت ^{[ 7 ] [ 8 ] [ 9 ]} أنه إذا كان الرسم البياني قابلاً للتلوين بـ k وجه، فإن G يقبل تدفقًا من الرتبة k لا يساوي الصفر في أي مكان . ويتحقق التكافؤ إذا كان السطح كرويًا.

التلوين غير المُصنَّف للرسم البياني هو مدارٌ للتلوين تحت تأثير مجموعة التشاكل الذاتي للرسم البياني. تبقى الألوان مُصنَّفة، بينما يبقى الرسم البياني نفسه غير مُصنَّف. يوجد نظيرٌ لكثير الحدود اللوني الذي يحسب عدد التلوينات غير المُصنَّفة للرسم البياني من مجموعة ألوان محدودة مُعطاة.

إذا فسرنا تلوين رسم بياني على d رأسًا على أنه متجه في${\displaystyle \mathbb {Z} ^{d}}$، إن فعل التشكل الذاتي هو تبديل للمعاملات في متجه التلوين.

يؤدي تخصيص ألوان مميزة لرؤوس مختلفة دائمًا إلى تلوين مناسب، لذلك

${\displaystyle 1\leq \chi (G)\leq n.}$

الرسوم البيانية الوحيدة التي يمكن تلوينها بلون واحد هي الرسوم البيانية عديمة الحواف . الرسم البياني الكامل${\displaystyle K_{n}}$يتطلب n رأسًا${\displaystyle \chi (K_{n})=n}$الألوان. في التلوين الأمثل، يجب أن يكون هناك على الأقل ضلع واحد من أضلاع الرسم البياني m بين كل زوج من فئات الألوان، لذلك

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}$

بشكل عام، عائلة${\displaystyle {\mathcal {F}}}$تكون مجموعة الرسوم البيانية محدودة بـ χ إذا كانت هناك دالة ما${\displaystyle c}$بحيث تكون الرسوم البيانية${\displaystyle G}$في${\displaystyle {\mathcal {F}}}$يمكن تلوينها بأقصى قدر${\displaystyle c(\omega (G))}$الألوان، أين${\displaystyle \omega (G)}$هو رقم الزمرة لـ${\displaystyle G}$بالنسبة لعائلة الرسوم البيانية المثالية، تكون هذه الدالة${\displaystyle c(\omega (G))=\omega (G)}$.

الرسوم البيانية القابلة للتلوين بلونين هي بالضبط الرسوم البيانية ثنائية الأجزاء ، بما في ذلك الأشجار والغابات. وبحسب نظرية الألوان الأربعة، يمكن تلوين أي رسم بياني مستوٍ بأربعة ألوان.

يُظهر التلوين الجشع أنه يمكن تلوين كل رسم بياني بلون واحد أكثر من درجة الرأس القصوى .

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

تحتوي الرسوم البيانية الكاملة على${\displaystyle \chi (G)=n}$و${\displaystyle \Delta (G)=n-1}$والدورات الفردية لها${\displaystyle \chi (G)=3}$و${\displaystyle \Delta (G)=2}$لذا، بالنسبة لهذه الرسوم البيانية، يُعد هذا الحد هو الأفضل الممكن. في جميع الحالات الأخرى، يمكن تحسين الحد قليلاً؛ تنص نظرية بروكس ^{[ 10 ]} على أن

نظرية بروكس :${\displaystyle \chi (G)\leq \Delta (G)}$بالنسبة للرسم البياني البسيط المتصل G ، إلا إذا كان G رسمًا بيانيًا كاملاً أو دورة فردية.

تم اكتشاف العديد من الحدود الدنيا للعدد اللوني على مر السنين:

إذا احتوت المجموعة G على مجموعة فرعية بحجم k ، فإن تلوين تلك المجموعة الفرعية يتطلب على الأقل k لونًا؛ بعبارة أخرى، يكون العدد اللوني على الأقل هو عدد المجموعة الفرعية:

${\displaystyle \chi (G)\geq \أوميغا (G).}$

بالنسبة للرسوم البيانية المثالية، يكون هذا الحد دقيقاً. ويُعرف إيجاد الزمر باسم مشكلة الزمر .

قيد هوفمان: دع${\displaystyle W}$لتكن مصفوفة متناظرة حقيقية بحيث${\displaystyle W_{i,j}=0}$حينما${\displaystyle (i,j)}$لا يمثل ذلك ميزة في${\displaystyle G}$. يُعرِّف${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$، أين${\displaystyle \lambda _{\max }(W)،\lambda _{\min }(W)}$أكبر وأصغر القيم الذاتية لـ${\displaystyle W}$. يُعرِّف${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$، مع${\displaystyle W}$كما سبق. ثم:

${\displaystyle \chi _{H}(G)\leq \chi (G).}$

العدد اللوني المتجهي :ليكن${\displaystyle W}$لتكن مصفوفة شبه موجبة محددة بحيث${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$حينما${\displaystyle (i,j)}$يُعدّ ذلك ميزة في${\displaystyle G}$. يُعرِّف${\displaystyle \chi _{V}(G)}$أن تكون أصغر قيمة لـ k التي تحقق هذه المصفوفة${\displaystyle W}$موجود. إذن

${\displaystyle \chi _{V}(G)\leq \chi (G).}$

عدد لوفاس : يُعد عدد لوفاس للرسم البياني التكميلي أيضًا حدًا أدنى للعدد اللوني:

${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

العدد اللوني الكسري : يمثل العدد اللوني الكسري للرسم البياني حدًا أدنى للعدد اللوني أيضًا:

${\displaystyle \chi _{f}(G)\leq \chi (G).}$

تم ترتيب هذه الحدود على النحو التالي:

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

تتميز الرسوم البيانية ذات المجموعات الكبيرة بعدد لوني عالٍ، ولكن العكس ليس صحيحًا. يُعدّ رسم غروتزش مثالًا على رسم بياني رباعي الألوان بدون مثلث، ويمكن تعميم هذا المثال على رسوم ميسيلسكيان .

النظرية ( WT Tutte ، 1947 ، ^{[ 11 ]} ألكسندر زيكوف 1949 ، جان ميتشيلسكي 1955 ): توجد رسوم بيانية خالية من المثلثات ذات عدد لوني عالي بشكل تعسفي.  

ولإثبات ذلك، قدّم كلٌّ من ميتشيلسكي وزيكوف بناءً لعائلة من الرسوم البيانية الخالية من المثلثات، مُعرَّفة استقرائيًا ، ولكن برقم لوني كبير كيفيًا. ^{[ 12 ]} وقد أنشأ بيرلينغ (1965) مربعات محاذية للمحاور في${\displaystyle \mathbb {R} ^{3}}$تتميز هذه المجموعة من الرسوم البيانية بخلوّ مخطط تقاطعها من المثلثات، ويتطلب تلوينها عددًا غير محدود من الألوان. تُسمى هذه المجموعة من الرسوم البيانية برسوم بورلينغ البيانية. وقد استُخدمت نفس الفئة من الرسوم البيانية لإنشاء مجموعة من القطع المستقيمة الخالية من المثلثات في المستوى، كما ورد في دراسة باوليك وآخرون (2014). ^{[ 13 ]} وتُظهر هذه الدراسة أن العدد اللوني لمخطط تقاطعها كبير جدًا أيضًا. وبالتالي، فإن هذا يعني أن المربعات المحاذية للمحاور في${\displaystyle \mathbb {R} ^{3}}$بالإضافة إلى القطع المستقيمة في${\displaystyle \mathbb {R} ^{2}}$ليست محدودة بـ χ . ^{[ 13 ]}

بحسب نظرية بروكس، يجب أن تتمتع الرسوم البيانية ذات العدد اللوني العالي بدرجة قصوى عالية. لكن قابلية التلوين ليست ظاهرة محلية تمامًا: فالرسم البياني ذو المحيط الكبير يبدو محليًا كشجرة، لأن جميع دوراته طويلة، لكن عدده اللوني ليس بالضرورة أن يكون 2.

نظرية ( إردوش ): توجد رسوم بيانية ذات محيط وعدد لوني عاليين بشكل تعسفي. ^{[ 14 ]}

تلوين حواف الرسم البياني G هو تلوين رؤوس الرسم البياني الخطي الخاص به${\displaystyle L(G)}$والعكس صحيح. وهكذا،

${\displaystyle \chi '(G)=\chi (L(G)).}$

توجد علاقة قوية بين قابلية تلوين الحواف وأقصى درجة للرسم البياني${\displaystyle \Delta (G)}$بما أن جميع الحواف المتصلة بنفس الرأس تحتاج إلى لون خاص بها، فإننا نحصل على

${\displaystyle \chi '(G)\geq \Delta (G).}$

علاوة على ذلك،

نظرية كونيغ :${\displaystyle \chi '(G)=\Delta (G)}$إذا كانت G ثنائية الأجزاء.

بشكل عام، تكون العلاقة أقوى مما تنص عليه نظرية بروكس لتلوين الرؤوس:

نظرية فيزينغ: رسم بياني ذو درجة قصوى${\displaystyle \Delta }$له عدد لوني حافّي${\displaystyle \Delta }$أو${\displaystyle \Delta +1}$.

يكون للرسم البياني k لون إذا وفقط إذا كان له اتجاه غير دوري يكون فيه أطول مسار بطول k على الأكثر ؛ هذه هي نظرية Gallai–Hasse–Roy–Vitaver ( Nešetřil & Ossona de Mendez 2012 ) .

بالنسبة للرسوم البيانية المستوية، فإن تلوين الرؤوس هو في الأساس ثنائي للتدفقات التي لا تحتوي على أي صفر .

لا يُعرف الكثير عن الرسوم البيانية اللانهائية. فيما يلي اثنتان من النتائج القليلة المتعلقة بتلوين الرسوم البيانية اللانهائية:

• إذا كانت جميع الرسوم البيانية الجزئية المحدودة لرسم بياني غير محدود G قابلة للتلوين بـ k لون، فإن G نفسه قابل للتلوين أيضًا ، بافتراض بديهية الاختيار . هذه هي نظرية دي بروين-إردوش لدي بروين وإردوش (1951) .
• إذا كان الرسم البياني يقبل تلوينًا كاملاً من الدرجة n لكل n ≥ n ₀ ، فإنه يقبل تلوينًا كاملاً لانهائيًا ( Fawcett 1978 ) .

كما ذكر أعلاه،${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$من بين التخمينات التي طرحها ريد عام 1998 أن القيمة أقرب في جوهرها إلى الحد الأدنى.${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

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

عندما قدم بيركوف ولويس متعددة الحدود اللونية في هجومهما على نظرية الألوان الأربعة ، افترضا أنه بالنسبة للرسوم البيانية المستوية${\displaystyle G}$، متعددة الحدود${\displaystyle P(G,t)}$لا توجد أصفار في المنطقة${\displaystyle [4,\infty )}$على الرغم من أنه من المعروف أن مثل هذه المعادلة اللونية لا تحتوي على أصفار في المنطقة${\displaystyle [5,\infty )}$وذلك${\displaystyle P(G,4)\neq 0}$لا تزال فرضيتهم دون حل. كما لا تزال مشكلة تحديد خصائص الرسوم البيانية التي لها نفس متعددة الحدود اللونية وتحديد أي من متعددات الحدود لونية مشكلة لم تُحل.

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

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

تعتمد عملية البحث الشامل عن تلوين k لونًا على كل من${\displaystyle k^{n}}$يتم تخصيص k لونًا لـ n رأسًا، ويتم التحقق من كل منها للتأكد من صحتها. لحساب العدد اللوني ومتعدد الحدود اللوني، تُستخدم هذه العملية لكل${\displaystyle k=1,\ldots ,n-1}$، غير عملي لجميع الرسوم البيانية المدخلة باستثناء أصغرها.

باستخدام البرمجة الديناميكية وحدود على عدد المجموعات المستقلة القصوى ، يمكن تحديد قابلية التلوين k في الوقت والمكان${\displaystyle O(2.4423^{n})}$[ ^{16 ]} باستخدام مبدأ الإدراج والاستبعاد وخوارزمية ييتس للتحويل السريع لزيتا، يمكن تحديد إمكانية التلوين بـ k لون ^في وقت${\displaystyle O(2^{n}n)}$^{[ 15 ] [ 17 ] [ 18 ] [ 19 ]} لأي قيمة لـk. توجد خوارزميات أسرع معروفة لإمكانية التلوين بثلاثة وأربعة ألوان، والتي يمكن تحديدها في وقت${\displaystyle O(1.3289^{n})}$^{[ 20 ]} و${\displaystyle O(1.7272^{n})}$[ ^{21 ] على التوالي. كما تُعرف خوارزميات أسرع بشكل كبير للرسوم البيانية} ذات 5 و6 ألوان، وكذلك للعائلات المحدودة من الرسوم البيانية، بما في ذلك الرسوم البيانية المتفرقة. ^{[ 22 ]}

الانقباض​${\displaystyle G/uv}$الرسم البياني G هو الرسم البياني الناتج عن تحديد الرأسين u و v ، وإزالة أي حواف بينهما. الحواف المتبقية المتصلة أصلاً بـ u أو v تصبح الآن متصلة بتحديدهما ( أي العقدة المدمجة الجديدة uv ). تلعب هذه العملية دورًا رئيسيًا في تحليل تلوين الرسوم البيانية.

يحقق العدد اللوني العلاقة التكرارية التالية :

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

بسبب زيكوف (1949) ، حيث u و v رأسان غير متجاورين، و${\displaystyle G+uv}$هي الرسم البياني مع إضافة الحافة uv . تعتمد العديد من الخوارزميات على تقييم هذه العلاقة التكرارية، وتُسمى شجرة الحساب الناتجة أحيانًا شجرة زيكوف. يعتمد وقت التشغيل على طريقة استدلالية لاختيار الرؤوس u و v .

تحقق متعددة الحدود اللونية علاقة التكرار التالية

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k),}$

حيث u و v رأسان متجاوران، و${\displaystyle G-uv}$هل هذا هو الرسم البياني بعد إزالة الحافة uv ؟${\displaystyle P(G-uv,k)}$يمثل هذا العدد عدد التلوينات الصحيحة الممكنة للرسم البياني، حيث قد تكون رؤوسه متشابهة أو مختلفة الألوان. تنشأ هذه التلوينات الصحيحة من رسمين بيانيين مختلفين. على سبيل المثال، إذا كان للرأسين u و v لونان مختلفان، فيمكننا اعتبار رسم بياني يكون فيه u و v متجاورين. أما إذا كان لهما نفس اللون ، فيمكننا اعتبار رسم بياني يكون فيه u و v متقاربين. قاد فضول توت حول خصائص الرسم البياني الأخرى التي تحقق هذه العلاقة التكرارية إلى اكتشاف تعميم ثنائي المتغيرات لكثير الحدود اللوني، وهو كثير حدود توت .

تُنتج هذه التعبيرات إجراءً تكراريًا يُسمى خوارزمية الحذف والانكماش ، والتي تُشكل أساسًا للعديد من خوارزميات تلوين الرسوم البيانية. ويخضع وقت التشغيل لنفس علاقة التكرار التي تخضع لها أعداد فيبوناتشي ، لذا في أسوأ الحالات، تعمل الخوارزمية في وقت لا يتجاوز عاملًا متعدد الحدود.${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$لـ n رأسًا و m حافة. ^{​​[ 23 ]} يمكن تحسين التحليل بحيث يكون ضمن عامل متعدد الحدود للعدد${\displaystyle t(G)}$من الأشجار الممتدة للرسم البياني المُدخل. ^{[ 24 ]} عمليًا، تُستخدم استراتيجيات التفرع والتقييد ورفض تماثل الرسم البياني لتجنب بعض الاستدعاءات المتكررة. يعتمد وقت التشغيل على الطريقة الاستدلالية المستخدمة لاختيار زوج الرؤوس.

تأخذ الخوارزمية الجشعة الرؤوس في الاعتبار بترتيب محدد${\displaystyle v_{1}}$...${\displaystyle v_{n}}$ويسند إلى${\displaystyle v_{i}}$أصغر لون متاح غير مستخدم من قبل${\displaystyle v_{i}}$جيرانه بين${\displaystyle v_{1}}$...${\displaystyle v_{i-1}}$مع إضافة لون جديد عند الحاجة. تعتمد جودة التلوين الناتج على الترتيب المُختار. يوجد ترتيب يؤدي إلى تلوين جشع بالعدد الأمثل من${\displaystyle \chi (G)}$الألوان. من ناحية أخرى، يمكن أن تكون التلوينات الجشعة سيئة بشكل تعسفي؛ على سبيل المثال، يمكن تلوين الرسم البياني التاجي على n رأسًا بلونين، ولكن له ترتيب يؤدي إلى تلوين جشع مع${\displaystyle n/2}$الألوان.

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

إذا تم ترتيب الرؤوس وفقًا لدرجاتها ، فإن التلوين الجشع الناتج يستخدم على الأكثر${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$عدد الألوان، بحد أقصى لون واحد يزيد عن أعلى درجة في الرسم البياني. تُعرف هذه الطريقة الاستدلالية أحيانًا باسم خوارزمية ويلش-باول. ^{[ 25 ]} وهناك طريقة استدلالية أخرى من ابتكار بريلاز ، تُحدد الترتيب ديناميكيًا أثناء تقدم الخوارزمية، حيث يتم اختيار الرأس المجاور لأكبر عدد من الألوان المختلفة. ^{[ 26 ]} وتعتمد العديد من الطرق الاستدلالية الأخرى لتلوين الرسوم البيانية على التلوين الجشع لاستراتيجية ثابتة أو ديناميكية محددة لترتيب الرؤوس، وتُسمى هذه الخوارزميات أحيانًا بخوارزميات التلوين التسلسلي .

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

هناك طريقتان معروفتان للتلوين متعدد الحدود هما خوارزمية DSatur وخوارزمية RLF ( الأكبر أولاً) المتكررة .

على غرار خوارزمية التلوين الجشعة ، تقوم خوارزمية DSatur بتلوين رؤوس الرسم البياني واحدًا تلو الآخر، مستخدمةً لونًا غير مستخدم سابقًا عند الحاجة. بمجرد تلوين رأس جديد ، تحدد الخوارزمية أيًّا من الرؤوس المتبقية غير الملونة يحتوي على أكبر عدد من الألوان المختلفة في جواره، ثم تقوم بتلوين هذا الرأس تاليًا. يُعرف هذا بدرجة تشبع رأس معين.

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

أسوأ حالة تعقيد لـ DSatur هي${\displaystyle O(n^{2})}$، أين${\displaystyle n}$يمثل عدد الرؤوس في الرسم البياني. يمكن أيضًا تنفيذ الخوارزمية باستخدام كومة ثنائية لتخزين درجات التشبع، وتعمل في${\displaystyle O((n+m)\log n)}$أين${\displaystyle m}$يمثل عدد الحواف في الرسم البياني. ^{[ 27 ]} ينتج عن ذلك عمليات تشغيل أسرع بكثير مع الرسوم البيانية المتفرقة. التعقيد الإجمالي لـ RLF أعلى قليلاً من DSatur عند${\displaystyle O(mn)}$[ ^{27 ]​}

تُعتبر DSatur و RLF دقيقتين بالنسبة للرسوم البيانية ثنائية الأجزاء والدورات والعجلات . ^{[ 27 ]}

من المعروف أنه يمكن تلوين الرسم البياني ذي اللون χ بـ c لونًا في النموذج المحلي الحتمي، في${\displaystyle O(n^{1/\alpha })}$جولات، مع${\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }$. حد أدنى مطابق لـ${\displaystyle \Omega (n^{1/\alpha })}$كما هو معروف، فإن عدد الجولات هو 1. ويظل هذا الحد الأدنى قائماً حتى في حالة السماح باستخدام أجهزة الكمبيوتر الكمومية التي يمكنها تبادل المعلومات الكمومية، ربما باستخدام حالة متشابكة مشتركة مسبقاً.

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

في الرسم البياني المتناظر ، لا تستطيع الخوارزمية الموزعة الحتمية إيجاد تلوين مناسب للرؤوس. يلزم توفر بعض المعلومات المساعدة لكسر التناظر. يفترض عادةً أن لكل عقدة مُعرّفًا فريدًا في البداية ، على سبيل المثال، من المجموعة {1، 2، ...، n } . بعبارة أخرى، نفترض أن لدينا تلوينًا من n لونًا. يكمن التحدي في تقليل عدد الألوان من n إلى، على سبيل المثال، Δ  +  1. كلما زاد عدد الألوان المستخدمة، مثلاً O (Δ) بدلاً من Δ  +  1، قلّت جولات الاتصال المطلوبة. ^{[ 28 ]}

يتطلب الإصدار الموزع المباشر للخوارزمية الجشعة للتلوين (Δ  + 1) Θ( n ) جولة اتصال في أسوأ الحالات - قد يلزم نشر المعلومات من جانب واحد من الشبكة إلى جانب آخر. 

أبسط الحالات المثيرة للاهتمام هي دورة n . يُبين ريتشارد كول وأوزي فيشكين ^{[ 29 ]} وجود خوارزمية موزعة تُقلل عدد الألوان من n إلى O (log n ) في خطوة اتصال متزامنة واحدة. بتكرار الإجراء نفسه، يُمكن الحصول على تلوين ثلاثي لدورة n في O ( log * n ) خطوة اتصال (بافتراض وجود مُعرفات عقد فريدة).  

الدالة log * ، أو اللوغاريتم المتكرر ، هي دالة بطيئة النمو للغاية، "شبه ثابتة". ولذلك، أثارت نتيجة كول وفيشكين تساؤلاً حول إمكانية وجود خوارزمية موزعة ذات زمن ثابت لتلوين دورة n بثلاثة ألوان . وقد أثبت لينال (1992) أن هذا غير ممكن: إذ تتطلب أي خوارزمية موزعة حتمية Ω( log * n ) من خطوات الاتصال لاختزال تلوين n إلى تلوين ثلاثة ألوان في دورة n . 

يمكن تطبيق تقنية كول وفيشكين على الرسوم البيانية ذات الدرجات المحدودة أيضًا؛ حيث يبلغ زمن التشغيل poly(Δ) + O ( log * n ). ^{[ 30 ]} وقد وُسِّعت هذه التقنية لتشمل الرسوم البيانية القرصية الوحدوية بواسطة شنايدر وواتنهوفر. ^{[ 31 ]} أما أسرع الخوارزميات الحتمية لتلوين (Δ + 1) للقيم الصغيرة لـ Δ، فتعود إلى ليونيد بارينبويم ومايكل إلكين وفابيان كون. ^{[ 32 ]} وتعمل خوارزمية بارينبويم وآخرون في زمن O (Δ) + log * ( n )/2، وهو الأمثل من حيث n نظرًا لعدم إمكانية تحسين العامل الثابت 1/2 بسبب الحد الأدنى لـ Linial. ويستخدم بانكونيسي وسرينيفاسان (1996) تفكيكات الشبكة لحساب تلوين Δ+1 في زمن     ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$.

تمت دراسة مشكلة تلوين الحواف أيضًا في النموذج الموزع. حقق بانكونيسي وريزي (2001) تلوينًا بمقدار (2Δ − 1) في زمن قدره O (Δ + log * n ) في هذا النموذج. وينطبق الحد الأدنى لتلوين الرؤوس الموزع، الذي وضعه لينال (1992)، على مشكلة تلوين الحواف الموزعة أيضًا.     

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

يُعدّ تلوين الرسوم البيانية عمليةً صعبةً حسابيًا. وتُصنّف مسألة تحديد ما إذا كان رسم بياني مُعطى يقبل تلوينًا بـ k لونًا لقيمة k مُعطاة ضمن فئة NP-complete، باستثناء الحالات التي يكون فيها k ∈ { 0, 1, 2 } . وعلى وجه الخصوص، تُصنّف مسألة حساب العدد اللوني ضمن فئة NP-hard. [ ^{34 ] وتبقى} مسألة التلوين الثلاثي NP-complete حتى على الرسوم البيانية المستوية المنتظمة من الدرجة 4. ^{[ 35 ]} ومع ذلك، بالنسبة للرسوم البيانية ذات الدرجة القصوى 3 أو أقل، تُشير نظرية بروكس إلى إمكانية حلّ مسألة التلوين الثلاثي في ​​زمن خطي. علاوةً على ذلك، لكل k > 3، يوجد تلوين k لونًا لرسم بياني مستوٍ وفقًا لنظرية الألوان الأربعة ، ومن الممكن إيجاد هذا التلوين في زمن متعدد الحدود. ومع ذلك، فإن إيجاد أصغر تلوين رباعي معجميًا لرسم بياني مستوٍ يُعدّ NP-complete. ^{[ 36 ]}

تحسب أفضل خوارزمية تقريب معروفة تلوينًا بحجم لا يتجاوز عامل O ( n (log  log n ) ^² (log n) ^⁻³ ) من العدد اللوني. ^{[ 37 ]} بالنسبة لجميع قيم ε > 0، فإن تقريب العدد اللوني ضمن ^n¹⁻ε يُعد مسألة صعبة من ^{نوع NP} . ^{[ 38 ]}    

كما أن تلوين رسم بياني قابل للتلوين بثلاثة ألوان بخمسة ألوان، ^{[ 39 ]} ورسم بياني قابل للتلوين بأربعة ألوان بسبعة ألوان، ^{[ 39 ]} ورسم بياني قابل للتلوين بـ k لونًا بـ${\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1}$الألوان لـ k ≥ 5. ^{[ 40 ]}

يُعد حساب معاملات متعددة الحدود اللونية مسألة صعبة من فئة #P . في الواقع، حتى حساب قيمة${\displaystyle \chi (G,k)}$تُعتبر المسألة صعبة من فئة P عند أي نقطة نسبية k باستثناء k  =  1 و k  =  2. ^{[ 41 ]} لا يوجد حل FPRAS لتقييم متعددة الحدود اللونية عند أي نقطة نسبية k  ≥  1.5 باستثناء k  =  2 إلا إذا كانت NP  = RP . ^{[ 42 ]} 

فيما يخص تلوين الحواف، يُقدّم برهان نتيجة فيزينغ خوارزمية تستخدم على الأكثر Δ+1 لونًا. مع ذلك، فإنّ تحديد القيمة المُرشّحة للعدد اللوني للحافة من بين القيمتين المُحتملتين يُعدّ مسألةً كاملةً من فئة NP. ^{[ 43 ]} من حيث خوارزميات التقريب، تُبيّن خوارزمية فيزينغ إمكانية تقريب العدد اللوني للحافة بدقة تصل إلى 4/3، وتُظهر نتيجة الصعوبة عدم وجود خوارزمية (4/3 − ε ) لأي قيمة ε > 0 إلا إذا كانت P = NP . تُعدّ هذه النتائج من أقدم النتائج في أدبيات خوارزميات التقريب، على الرغم من عدم استخدام أيٍّ من الورقتين البحثيتين لهذا المفهوم بشكلٍ صريح. ^{[ 44 ]}    

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

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

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

يتمثل النهج المتبع في الكتب الدراسية لحل هذه المشكلة في نمذجتها كمسألة تلوين رسم بياني. ^{[ 46 ]} يقوم المترجم بإنشاء رسم بياني للتداخل ، حيث تمثل الرؤوس متغيرات، ويربط ضلع بين رأسين إذا كانا مطلوبين في الوقت نفسه. إذا أمكن تلوين الرسم البياني بـ k لونًا، فإنه يمكن تخزين أي مجموعة من المتغيرات المطلوبة في الوقت نفسه في k سجل على الأكثر.

تظهر مشكلة تلوين الرسم البياني في العديد من المجالات العملية مثل جدولة المباريات الرياضية، ^{[ 47 ]} وتصميم مخططات الجلوس، ^{[ 48 ]} وجدولة الامتحانات، ^{[ 49 ]} وجدولة سيارات الأجرة، ^{[ 50 ]} وحل ألغاز سودوكو . ^{[ 51 ]}

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

التلوين المعياري هو نوع من أنواع تلوين الرسوم البيانية حيث يكون لون كل رأس هو مجموع ألوان الرؤوس المجاورة له.

يترك${\displaystyle k\geq 2}$عدد من الألوان حيث${\displaystyle \mathbb {Z} _{k}}$هي مجموعة الأعداد الصحيحة modulo${\displaystyle k}$يتكون من العناصر (أو الألوان)${\displaystyle 0,1,2,...,k-2,k-1}$أولاً، نقوم بتلوين كل رأس في${\displaystyle G}$باستخدام عناصر${\displaystyle \mathbb {Z} _{k}}$مما يسمح بتعيين نفس اللون لرأسين متجاورين. بعبارة أخرى، نريد${\displaystyle c}$أن يكون لونًا بحيث${\displaystyle c:V(G)\rightarrow \mathbb {Z} _{k}}$حيث يمكن تعيين نفس اللون للرؤوس المتجاورة.

لكل رأس${\displaystyle v}$في${\displaystyle G}$، مجموع ألوان${\displaystyle v}$،${\displaystyle \sigma (v)}$، هو مجموع جميع الرؤوس المجاورة لـ${\displaystyle v}$modulo${\displaystyle k}$مجموع ألوان${\displaystyle v}$يُرمز إليه بـ

${\displaystyle \sigma (v)=\sum _{u\in N(v)}c(u),}$

أين${\displaystyle u}$هو رأس عشوائي في جوار${\displaystyle v}$،${\displaystyle N(v)}$ثم نلون كل رأس باللون الجديد المحدد بمجموع ألوان الرؤوس المجاورة. الرسم البياني${\displaystyle G}$يتميز بتصميم معياري${\displaystyle k}$التلوين - إذا، لكل زوج من الرؤوس المتجاورة${\displaystyle a}$و${\displaystyle b}$،${\displaystyle \sigma (a)\neq \sigma (b)}$العدد اللوني المعياري لـ${\displaystyle G}$،${\displaystyle mc(G)}$، هي القيمة الدنيا لـ${\displaystyle k}$بحيث يوجد نمط معياري${\displaystyle k}$-تلوين${\displaystyle G}$.

على سبيل المثال، لنفترض وجود رأس${\displaystyle v}$مجاورة للرؤوس ذات الألوان المخصصة${\displaystyle 0,1,1}$، و${\displaystyle 3{\bmod {4}}}$(إنه،${\displaystyle k=4}$سيكون مجموع الألوان كالتالي:${\displaystyle \sigma (v)=(0+1+1+3){\bmod {4}}=5{\bmod {4}}=1{\bmod {4}}}$سيكون هذا هو اللون الجديد للرأس${\displaystyle v}$سنكرر هذه العملية لكل رأس في${\displaystyle G}$إذا لم يكن لأي من الرؤوس المتجاورة مجموع ألوان متساوٍ،${\displaystyle G}$يحتوي على معامل${\displaystyle 4}$تلوين.

يمكن أيضًا مراعاة التلوين للرسوم البيانية الموقعة ورسوم الربح البيانية .