צביעת קשתות

צביעה של הגרף השלם על שמונה קודקודים

צביעת קשתות של גרף היא השמה של צבעים לקשתות הגרף כך שלשום קודקוד אין זוג קשתות הנוגעות בו וצבועות באותו הצבע. בעיית הצביעה ב-K צבעים היא השאלה האם ניתן לעשות זאת עם קבוצה של K צבעים. דרך אחרת לנסח זאת היא לשאול האם ניתן לחלק את קשתות הגרף ל-K קבוצות כך שכל קבוצה מהווה שידוך. האינדקס הכרומטי של גרף הוא המספר הקטן ביותר של צבעים בו ניתן לצבוע את קשתות הגרף. בגרף שדרגתו המקסימלית היא d חייבים להשתמש בלפחות d צבעים (על פי עקרון שובך היונים). גרפים מסוימים ניתנים לצביעה ב-d צבעים: מעגל זוגי ניתן לצביעה בשני צבעים, הגרף השלם על 2n קודקודים ניתן לצביעה ב d=2n-1 צבעים (ראו דוגמה בציור) וכל גרף דו-צדדי ניתן לצביעה ב- d צבעים (הדבר נובע ממשפט קניג (König)). לעומת זאת מעגל אי-זוגי ניתן לצביעה רק בשלושה צבעים.

משפט ויזינג (נקרא על שמו של ואדים ויזינג שפרסם אותו ב-1964) קובע כי כל גרף פשוט (ללא קשתות מקבילות) ניתן לצביעה ב d+1 צבעים. כלומר האינדקס הכרומטי שלו הוא d או d+1. לגבי גרפים שאינם פשוטים (מולטיגרפים), קלוד שנון הראה כי האינדקס הכרומטי חסום על ידי ${\frac {3}{2}}d$ וביטוי זה הדוק במובן שיש גרפים לגביהם זה האינדקס הכרומטי. למרות האפיון ההדוק יחסית של משפט ויזינג, ההכרעה האם האינדקס הכרומטי של גרף נתון הוא d או d+1 היא בעיה NP-שלמה והדבר נכון גם לגרפים שדרגתם 3, כפי שהראה הולייר.

צביעה בארבעה צבעים של גרף פיטרסן

גרפים d רגולריים (כאלה שהדרגה של כל הקודקודים היא d) ניתנים לצביעה ב-d או d+1 צבעים. גרף פיטרסן (ראו תמונה) הוא דוגמה לגרף שלוש רגולרי שהאינדקס הכרומטי שלו הוא ארבע.

לגרפים דו-צדדיים יש אלגוריתמים מאוד יעילים למציאת צביעה ב-d צבעים, כאלה שזמן הריצה שלהם הוא $O(m\log d)$ .

תחום נוסף בתורת הגרפים הקשור בצביעה הוא צביעה של קודקודים. ניתן לנסח את בעיית הצביעה בקשתות של גרף כבעיית הצביעה בקודקודים של גרף הקשתות (line graph) של הגרף.

ראו גם

• סנרק (תורת הגרפים)
• בעיית צביעת המסלולים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

32171756צביעת קשתות