====== رنگ‌آمیزی مشروط ======

$G$ یک گراف ساده‌ی بی‌جهت است.

$\chi_s(G)$ را این گونه تعریف می‌کنیم: کم‌ترین تعداد رنگی که با آن بتوان $G$ را رنگ‌آمیزی معتبر کرد، به صورتی که هیچ مسیر ۴-راسی دو رنگی در $G$ نباشد.

$a(G)$ را این‌گونه تعریف می‌کنیم: کم‌ترین تعداد رنگی که با آن بتوان $G$ را رنگ‌آمیزی معتبر کرد، به صورتی که هیچ دور دو رنگی در $G$ نباشد.

اثبات کنید: $a(G) \leq \chi_s(G) \leq  a(G) \times 2^{a(G)-1}$

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