برای عدد طبیعی $ k $، $ k $-رنگ‌آمیزی رأسی از گراف $ G $ عبارت است از نگاشت $ f : V(G) \\longrightarrow \\{1,2,...,k\\} $ که این رنگ‌آمیزی معتبر است اگر هر دو رأس مجاور با رنگ‌های غیریکسان رنگ‌آمیزی شده باشند. یک گراف $ G $ را $ k $-رنگ‌پذیر گوییم هرگاه $ G $ دارای یک‌ $ k $-رنگ‌آمیزی معتبر باشد. همچنین کم‌ترین تعداد رنگ‌هایی را که لازم است تا گراف $ G $، یک $ k $-رنگ‌آمیزی معتبر داشته باشد عدد رنگی گراف $ G $ می‌نامیم و آن را با $ \\chi ( G ) $ نمایش می‌دهیم. نوع دیگری از رنگ‌آمیزی که برای اولین بار به وسیله‌ی دانشمندان بزرگی مانند اردوش، رابین و تیلور در سال 1978 و ویزینگ در سال 1992 مطرح گردید، رنگ‌آمیزی لیستی است. فرض می‌کنیم برای هر رأس $ v $ از گراف $ G $ لیستی از رنگ‌ها به نام $ L(v) $ داده شده است؛ می‌خواهیم یک رنگ‌آمیزی-رأسی به نام $ c $ طوری انجام دهیم که برای هر رأس $ v $، $ c (v) \\in L(v) $. اگر بتوان چنین رنگ‌آمیزی را انجام داد، به گراف $ G $، $ L $-رنگ‌پذیر می‌‌گویند. گراف $ G $، $ k $-انتخاب‌پذیر است اگر برای هر لیست $ L $ با شرط $ \\vert L(v) \\vert = k $ برای هر $ \\ v \\in V(G) $، $ G $، $ L $-رنگ‌پذیر باشد. عدد انتخاب یا عدد رنگی-لیستی گراف $ G $ به کوچک‌ترین عدد طبیعی $ k $ گفته می‌شود که گراف $ G $، $ k $-انتخاب‌پذیر است و آن را با $ \\ ch(G) $ نمایش می‌دهند.