גרף n-צביע – הבדלי גרסאות

בעיית צביעת גרפים מופיעה בבעיות מגוונות כשאלגוריתמים בתחום זה שימושים בהקשר של בעיות של תזמון משימות, הקצאת [[אוגר (מחשבים)|אוגרים]], זיהוי תבניות ופתרון תשבצי [[סודוקו]].<ref name{{הערה|שם="Lewis2015">|Lewis, R. ''A Guide to Graph Colouring: Algorithms and Applications''. Springer International Publishers, 2015.</ref>}}

בבעיית הקצאת אוגרים, נדרש ה[[מהדר]] ל[[מיטוב אלגוריתמים|מטב]] את הקצאת האוגרים לגישה מהירה למשתנים שנמצאים בשימוש נרחב בתוכנית. פתרון קלאסי לבעיה זו הוא למדל אותה כבעיית צביעת גרפים,<ref>{{הערה|{{צ-מאמר|מחבר=G. J. Chaitin, G. J. Chaitin|שם=Register allocation & spilling via graph coloring, Register allocation & spilling via graph coloring|כתב עת=ACM SIGPLAN Notices|כרך=17|עמ=98, 98–105, 101|שנת הוצאה=1982-06-23|doi=10.1145/800230.806984, 10.1145/872726.806984|קישור=http://dl.acm.org/citation.cfm?id=800230.806984,%20http://dl.acm.org/citation.cfm?id=872726.806984}}</ref>}} כאשר המהדר בונה גרף תלויות, כאשר משתנים מיוצגים על ידי קודקודים וקשתות מחברות בין זוגות קודקודים אם המשתנים שלהם נדרשים באותו הזמן. מספר הצביעה של הגרף מגדיר את מספר האוגרים הנדרש לשמירת המשתנים בזמן נתון.