On coloring problems with local constraints