====== رنگ‌آمیزی جبلی ======


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

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

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]