גרף n-צביע
ויקיפדיה האנציקלופדיה encyclopedia
בתורת הגרפים, גרף -צביע הוא גרף שאפשר לצבוע את הקודקודים שלו ב-n צבעים, כך ששני קודקודים סמוכים אינם צבועים באותו צבע.
עבור גרף , מסמנים ב- את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא מספר הצביעה (או המספר הכרומטי) של הגרף.
עבור , ההכרעה האם היא בעיה NP שלמה. לגרף יש מספר כרומטי 2 אם ורק אם הוא דו-צדדי, ותכונה זו ניתנת לזיהוי בזמן ליניארי במספר הקשתות.