یک گراف ساده‌ی جهت‌دار در نظر بگیرید. یک رنگ‌آمیزی از رأس‌های این گراف را جبلی گوییم؛ هرگاه زیرگراف القایی روی رئوس هر رنگ، دور جهت‌دار نداشته باشد. به این ترتیب، یک گراف ساده‌ی جهت‌دار را $k$-رنگ‌پذیر گوییم؛ هرگاه بتواند با $k$ رنگ به صورت جبلی رنگ‌آمیزی شود.

فرض کنید $k$ یک عدد طبیعی و $D$ یک گراف ساده‌ی جهت‌دار باشد. می‌دانیم در $D$ به ازای هیچ عدد طبیعی $r$، دور جهت‌دار به طول $rk+1$ وجود ندارد. ثابت کنید $D$، $k$-رنگ‌پذیر است.

• سوال بعد
• سوال قبل