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