It's not, though. If the four corners are sharp, blue & red are not adjacent, nor are green & orange. You can re-paint blue to red and orange to green, and you're left with a proper 3-coloring. Alternately, if the grey pixel takes another color (say, red) so that blue, green and orange are all adjacent to it, then green & orange are not adjacent -- re-paint orange to green, and you get a 4-coloring. Finally, if the grey pixel is its own region, you're effectively back in the first case and you can paint it black to obtain a 3-coloring.