גרף n-צביע – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
Matanyabot (שיחה | תרומות) מ בוט החלפות: \1ליניארי |
||
שורה 3:
עבור גרף <math>\ G</math>, מסמנים ב-<math>\chi(G)</math> את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא '''מספר הצביעה''' (או '''המספר הכרומטי''') של הגרף.
עבור <math>\ k>2</math>, ההכרעה האם <math>\ \chi(G)=k</math> היא בעיה [[NP_(סיבוכיות)|NP שלמה]]. לגרף יש מספר כרומטי 2 אם ורק אם הוא [[גרף דו-צדדי|דו-צדדי]], ותכונה זו ניתנת לזיהוי בזמן
== חסמים על מספר הצביעה ==
| |||