تشخیص گراف های کوهن مکالی

Question

گرافی با چهار راس را در نظر بگیرید که از لحاظ شکلی مربعی است که یک ضلع آن را حذف کرده ایم.نشان دهید که این گراف کوهن مکالی است.آیا این گراف با گراف دو بخشی ایزومرف است.اگر جواب مثبت است تناقضی با قضیه ی 9.1.14 پیش نمی آید؟ در حالت کلی چگونه میتوان گراف های کوهن مکالی را از روی شکل تشخیص داد.

Answer 1

کوهن مکالی است از آنجایی که کردال است و برای گرافهای کردال کافیه $ unmixed $ باشند که به وضوح چنین است(تنها مجموعه پوشش راسی مینیمال آن مجموعه های $\{1,3\} $و$\{2,4\} $هستند)

اما این گراف را میتوان به صورت زیر نگاه کرد که در این صورت یک گراف دوبخشی است(برای هماهنگی با قضیه $9.1.14$ آن را به صورت زیر نمایش میدهیم)

در حالت کلی نمیتوان از روی ظاهر کوهن مکالی بودن گرافها را تشخیص داد اما قضایایی نظیر $9.3.14$و $9.1.14$ برای حالت های خاص ابزارهایی را به ما میدهند.

مثلا در کردالها کافیه $ unmixed $ باشند یعنی تمام مینیمال پوشش راسی ها دارای یک کاردینالیتی باشند.

Comments

ممنون از پاسختون.البته برای تشخیص کوهن مکالی بودن گراف کردال  انگار علاوه بر یکدست  بودن باید بشه  N رو به صورت اجتماع فست های دارای راس آزاد هم نوشت.که این گراف این ویژگی رو هم داره.بابت نوع برچسب بندی با 9.1.14 به تناقض میرسیدم که با پاسخ شما رفع شد.

---

یکدست بودن کافیه