גרף n-צביע
בתורת הגרפים, גרף -צביע הוא גרף שאפשר לצבוע את הקודקודים שלו ב-n צבעים, כך ששני קודקודים סמוכים אינם צבועים באותו צבע.
עבור גרף , מסמנים ב- את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא מספר הצביעה (או המספר הכרומטי) של הגרף.
עבור , ההכרעה האם היא בעיה NP שלמה. לגרף יש מספר כרומטי 2 אם ורק אם הוא דו-צדדי, ותכונה זו ניתנת לזיהוי בזמן לינארי במספר הקשתות.
חסמים על מספר הצביעה
עבור גרף עם צמתים מקבלים טריוויאלית ש-.
אם מסמנים ב את הדרגה המקסימלית של צומת ב- אז . תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור בכל תת-גרף מושרה של קיים צומת כך ש- אז . עבור תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור גרף שלם על n צמתים ו ועבור מעגל אי-זוגי ו ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם משפט ברוקס קובע כי לכל שאר הגרפים .
נסמן ב- את גודל הקליקה המקסימלית ב- אז . אם אי-שוויון זה הדוק עבור הגרף ועבור כל אחד מתתי הגרפים המושרים שלו, אז הגרף נקרא גרף מושלם.
נסמן ב- את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר, אז .
הפולינום הכרומטי
מספר הדרכים לצבוע גרף נתון G ב- צבעים נתון על ידי הצבה של בפולינום , הקרוי הפולינום הכרומטי של הגרף. פולינום זה, שאותו גילה ג'ורג' בירקהוף ב-1912, מקיים את נוסחת הרקורסיה , לכל קשת e בגרף, כאשר G-e הוא הגרף ללא הקשת האמורה, ו-G/e הוא הגרף המתקבל מכיווץ הקשת לנקודה.
ראו גם
נושאים בתורת הגרפים | ||
---|---|---|
הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |