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