צביעת קשתות

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

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

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

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

ראו גםעריכה

סנרק (תורת הגרפים)

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