Assign each vertex a color in {0..k-1} so no edge has same-colored endpoints. Locked-color vertices project out their color from every neighbor's allowed set.