سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:گراف:سوال ۲
سوال ۲
یک گراف همبند سادهی G داریم. به ازای هر زیرگراف القایی H از G، داریم: κ′(H)≤10. بیشینه و کمینهی χ(G) را بیابید.
فرض کنید n و Δ اعدادی طبیعی باشند. ثابت کنید شرط لازم و کافی برای آن که عدد رنگی یالی هر گراف سادهی n رأسی و m یالی با درجهی بیشینهی Δ، برابر Δ+1 باشد، آن است که \frac{(n-1)\Delta}{2} < m \le \frac{n\Delta}{2} و n فرد باشد.