גרף מושלם
ויקיפדיה האנציקלופדיה encyclopedia
בתורת הגרפים, גרף מושלם הוא גרף שבו בכל תת גרף מושרה, גודל הקליקה המקסימלית שווה למספר הצביעה של תת-הגרף.
צביעה חוקית של גרף G היא בפרט גם צביעה חוקית של כל תת-גרף שלו, לכן אם קיימת ב -G קליקה בגודל k אז כל צביעה חייבת להשתמש בלפחות k צבעים. מכאן שגודל הקליקה המקסימלית מהווה חסם תחתון על מספר הצביעה של הגרף. אם חסם זה הוא הדוק לכל תת-גרף מושרה של G, אז G נחשב מושלם.