سوال ۵
فرض کنید مجموعه ای از رنگ‍‌ها $C$ داده شده است. یک تخصیص لیستی از گراف $G$ به هر رأس گراف یک زیرمجموعه از $C$ نسبت می دهد به‌طوری‌که برای رنگ‌آمیزی هر رأس از گراف فقط می‌توانیم از رنگ‌های موجود در مجموعه مربوط به آن رأس استفاده کنیم.
به بیان دقیق‌تر اگر $L: V \rightarrow p(C)$ آنگاه مجموعه رنگ‌های مجاز هر راس $v$ ، $L(v)$ خواهد بود. با داشتن $L$ به یک گراف $L$-رنگ پذیر می‌گوییم اگر تابع $\phi: V \rightarrow C$ وجود داشته باشد که اولاً $\phi(v) \in L(v)$ و ثانیاً به ازای دو رأس مجاور $u$ و $v$ داشته باشیم: $\phi(u) \ne \phi(v)$.
به یک گراف $k$-انتخاب‌پذیر می‌گوییم هرگاه به ازای هر تخصیص $L$ که در آن به‌ازای هر رأس $|L(v)| \ge k$ برقرار باشد، گراف $L$-رنگ پذیر باشد. و به کوچک‌ترین $k$ای که گراف‌مان $k$-انتخاب‌پذیر باشد، عدد انتخاب $G$ گوییم و آن را با $ch(G)$ نشان می‌دهیم. برای مثال با دادن مجموعه‌های مساوی به هر راس ( $L(v) = \{1, \cdots , k\}$ ) می‌توان دید که $ch(G) \ge \chi(G)$ .
- ثابت کنید $ch(G) \leq deg(G) + 1 \leq \Delta(G) + 1$ (که $deg(G)$ عبارت است از ماکزیمم $\delta(H)$ روی تمام زیرگراف‌های $H$ از $G$).
- در ابتدا به نظر می‌رسد که مساله $k$-رنگ‌پذیری از مساله $k$-انتخاب‌پذیری سخت‌تر باشد، زیرا به نظر می‌رسد بدترین حالت این است که همه مجموعه‌ها مساوی باشند. ولی این گزاره صحیح نمی‌باشد.
- برای مثال نقض گرافی مثال بزنید که ۲-رنگ‌پذیر باشد و $ch(G) > 2$ .
- به ازای هر $k$ گرافی مثال بزنید که ۲-رنگ‌پذیر باشد و $ch(G) \ge k$.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
