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