קוגרף

בתורת הגרפים, קוגרף הוא גרף הנוצר מקודקודים בודדים על ידי הפעלות של איחוד זר ואופרטור הגרף המשלים (גרף שיש בו קשת אם"ם אין קשת בגרף המקורי).

דוגמאות לקוגרפים הם גרפים מלאים וגרפי טורן.

הגדרה

נגדיר באופן רקורסיבי:

• קודקוד בודד הוא קוגרף
• אם $G_1$ ו-$G_2$ הם קוגרפים זרים בקודקודים אז כך גם $G_1\cup G_2$
• אם $G$ קוגרף אז כך גם $\overline{G}$ (הגרף המשלים).

תכונות

היותו של גרף קוגרף שקולה לתכונות הבאות:

• הגרף לא מכיל את המסילה מאורך 3 כתת-גרף מושרה
• כל תת-גרף מושרה מקיים שכל קליקה מקסימלית וכל קבוצה בלתי תלויה מקסימלית נחתכות בקודקוד יחיד
• בכל תת-גרף מושרה עם לפחות 2 קודקודים יש שני קודקודים עם אותם שכנים
• כל צביעה חמדנית של כל תת-גרף מושרה היא אופטימלית

קישורים חיצוניים

• קוגרף באתר MathWorld
• תבנית:MathWorld

תבנית:קצרמר