سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:گراف:سوال ۶
سوال ۶
فرض کنید G=F∪H. ثابت کنید χ(G)≤χ(F)χ(H).
فرض کنیم D یک سودهی از G باشد و χ(G)>rs. فرض کنید هر v∈V(D) به یک عدد حقیق f(v) تخصیص داده شده است. ثابت کنید D دارای یک مسیر u0→⋯→ur با 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 است.