On the tractability of $(k,i)$-coloring