سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:گراف:سوال ۶
سوال ۶
فرض کنید $G = F \cup H$. ثابت کنید $\chi(G) \leq \chi(F)\chi(H)$.
فرض کنیم $D$ یک سودهی از $G$ باشد و $\chi(G) > rs$. فرض کنید هر $v \in V(D)$ به یک عدد حقیق $f(v)$ تخصیص داده شده است. ثابت کنید $D$ دارای یک مسیر $u_0 \rightarrow \cdots \rightarrow u_r$ با $f(u_0) \leq ... \leq f(u_r)$ و یا یک مسیر $v_0 \rightarrow \cdots \rightarrow v_s$ با $f(v_0) > \cdots > f(v_s)$ است.
با استفاده از قسمت قبل ثابت کنید که هر دنباله از $rs+1$ عدد حقیقی متمایز دارای یک زیردنباله افزایشی به اندازه $r+1$ و یا یک زیردنباله کاهشی به اندازه $s+1$ است.