גרף n-צביע

בתורת הגרפים, גרף $\ n$-צביע הוא גרף שאפשר לצבוע את הקודקודים שלו ב-n צבעים, כך ששני קודקודים סמוכים אינם צבועים באותו צבע.

עבור גרף $\ G$, מסמנים ב-$\chi(G) = \min\{k \mid G \;is\; k \;\mbox{colorable}\}$ את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא מספר הצביעה (או המספר הכרומטי) של הגרף.

עבור $\ k>2$, ההכרעה האם $\ \chi(G)=k$ היא בעיה NP שלמה. לגרף יש מספר כרומטי 2 אם ורק אם הוא דו-צדדי, ותכונה זו ניתנת לזיהוי בזמן לינארי במספר הקשתות.

חסמים על מספר הצביעה

עבור גרף $\ G$ עם $\ n$ צמתים מקבלים טריוויאלית ש-$1 \leq \chi(G) \leq n$.

אם מסמנים ב $\triangle(G)$ את הדרגה המקסימלית של צומת ב-$\ G$ אז $\chi(G)\leq \triangle(G)+1$. תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור $k\in \mathbb{N}$ בכל תת-גרף מושרה $\ H$ של $\ G$ קיים צומת $v\in H$ כך ש-$d_H (v)\leq k$ אז $\chi(G)\leq k+1$. עבור $k=\triangle(G)$ תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור גרף שלם על n צמתים $\triangle(G)=n-1$ ו $\ \chi(G) = n$ ועבור מעגל אי-זוגי $\triangle(G)=2$ ו $\ \chi(G) = 3$ ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם משפט ברוקס קובע כי לכל שאר הגרפים $\chi(G)\leq \triangle(G)$.

נסמן ב-$\ \omega(G)$ את גודל הקליקה המקסימלית ב-$\ G$ אז $\ \chi(G)\geq \omega(G)$. אם אי-שוויון זה הדוק עבור הגרף ועבור כל אחד מתתי הגרפים המושרים שלו, אז הגרף נקרא גרף מושלם.

נסמן ב-$\ \alpha(G)$ את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר, אז $\ \chi(G)\geq \frac{n}{\alpha(G)}$.

הפולינום הכרומטי

מספר הדרכים לצבוע גרף נתון G ב-$\ \lambda$ צבעים נתון על ידי הצבה של $\ \lambda$ בפולינום $\ \chi(G,\lambda)$, הקרוי הפולינום הכרומטי של הגרף. פולינום זה, שאותו גילה ג'ורג' בירקהוף ב-1912, מקיים את נוסחת הרקורסיה $\chi(G,\lambda) = \chi(G-e,\lambda) - \chi(G/e, \lambda)$, לכל קשת e בגרף, כאשר G-e הוא הגרף ללא הקשת האמורה, ו-G/e הוא הגרף המתקבל מכיווץ הקשת לנקודה.

ראו גם

• משפט ארבעת הצבעים

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.