فرض کنید مجموعه ای از رنگ‍‌ها ‎$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)$‎ .

1. ثابت کنید ‎$ch(G) \leq deg(G)‎ + ‎1 \leq \Delta(G)‎ + ‎1$‎ ‎ (که ‎$deg(G)$ عبارت‌ است از ماکزیمم ‎$\delta(H)$‎ روی تمام زیرگراف‌های ‎$H$‎ از ‎$G$‎).
2. در ابتدا به نظر می‌رسد که مساله ‎$k$‎-رنگ‌پذیری از مساله ‎$k$‎-انتخاب‌پذیری سخت‌تر ب‍‌اشد، زیرا به نظر می‌رسد بدترین حالت این است که همه مجموعه‌ها مساوی باشند. ولی این گزاره صحیح نمی‌باشد.
   1. برای مثال نقض گرافی مثال بزنید که ‎۲‎-رنگ‌پذیر باشد و ‎$ch(G) > 2$ ‎.
   2. به ازای هر ‎$k$‎ گرافی مثال بزنید که ‎۲‎-رنگ‌پذیر باشد و ‎$ch(G) \ge k$‎.

• سوال بعد
• سوال قبل