رنگ‌آمیزی گراف با گسترگراف

http://www.cs.yale.edu/homes/spielman/561/lect03-15.pdf

قضیه ویلف

همیشه k هست که می‌شود طوری رأسها را مرتب کرد که یالهای خروجی که به سمت رأسهای با اندیس کمتر هستند حداکثر k باشد. حالا یک گراف جهت‌دار داریم که حداکثر درجه‌اش k است پس با k+1 رنگ می‌شود رنگ‌آمیزیش کرد.

قضیه ویلف می‌گوید k<=mu_1 باشد همیشه این خاصیت را دارد.

متوسط درجه‌ی گراف حداکثر mu_1 است. چون همیشه یکی هست که از امید ریاضی کمتر است، بزرگترین کسی که این خاصیت را دارد انتخاب می‌کنیم و آخر می‌گذاریم. زیرگراف روی n-1 رأس دیگر را در نظر می‌گیریم. وقتی یک سطر یا ستون از یک ماتریس متقارن را حذف می‌کنیم، بزرگترین مقدار ویژه‌ی آن کمتر مساوی مقدار فعلی می‌شود. پس می‌شود همین عمل حذف کردن رأس را به ازای ماتریس مجاورت این زیرگراف ادامه بدهیم تا همه چیده شوند.

کران هافمن

می‌گوید می‌شود طوری رأسها را اندیس‌گذاری کرد که ماتریس مجاورتش به صورت یک ماتریس بلوکی با k بلوک و قطر صفر باشد که هر بلوکی متناظر یک رنگ است. حالا با استفاده از ویژگی‌های مقدار ویژه‌های ماتریس به این شکل یک کران به دست می‌آورد.