גרף n-צביע

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

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

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

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

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

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

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

נסמן ב-$\alpha (G)$ את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר, אז $\chi (G)\ge \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 הוא הגרף המתקבל מכיווץ הקשת לנקודה.

ראו גם

• משפט ארבעת הצבעים
• משפט לובאס-קנזר

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