كران‌هايي براي عدد رنگي r-پوياي گراف‌ها

فرض كنيد $ G $ يك گراف ساده باشد. يك رنگ‌آميزي $r$-پوياي $ G $ يك رنگ‌آميزي معتبر $G$ است به‌طوري‌كه در همسايگي هر رأس $ v $ از $ G $ حداقل $\min \lbrace r, {\rm \deg}(v)\rbrace$ رنگ مجزا ظاهر شود. به كم‌ترين $ k $‌اي كه $ G $ را بتـوان با $ k $ رنگ به صورت $ r$-پويا رنگ‌آميزي كرد، عدد رنگي $ r $-پوياي گراف $ G $ گفته مي‌شود و با نماد $\chi_{r}(G)$ نشان داده مي‌شود. با استفاده از يــك الــگــوريــتــم حــريـصـانـه نشان مي‌دهيم تحت شرايطي $\chi_{r}(G)\leq r\Delta(G)-1 $. هم‌چنين اگر $ G $ داراي $ k $-عامل باشد، نشان مي‌دهيم تحت شرايطي $ \chi_r(G)\leq r\chi(G) $ در حالتي‌كه $ k $ نسبت به $ r $ به‌اندازه كافي بزرگ باشد. در اين‌جا $ \chi(G) $ عدد رنگي $ G $ و $ \Delta(G) $ بزرگ‌ترين درجه رئوس $ G $ است.