You're thinking of Kempe chains, which are a tool used in:
- some proofs of the five-color theorem for planar graphs;
- Kempe's original (wrong) proof of the four-color theorem for planar graphs;
- Maybe a few other settings as well.
Let me try to explain the idea in the context of the five-color theorem. Here, we're trying to prove that all $n$-vertex planar graphs can be vertex-colored with at most $5$ colors, by induction on $n$.
We can show that in any planar graph, there is a vertex of degree at most $5$. If we're trying to $5$-color an $n$-vertex graph $G$, we can find a vertex $v$ with $\deg(v) \le 5$, and color $G-v$ first (by the induction hypothesis). We can extend this coloring to a coloring of $G$, by giving $v$ a color not used by its neighbors, unless $v$'s neighbors use all $5$ colors between them.
If $v$ has $5$ neighbors of $5$ different colors, we need to change the coloring of $G-v$ before we can complete it to a coloring of $G$. This is what Kempe chains are good for.
Suppose that two of the colors are red and yellow. We want to recolor $G-v$ so that $v$ does not have any red neighbors. To do that,
- We take $v$'s existing red neighbor $w$, and color it yellow.
- This may cause other conflicts, if $w$ had yellow neighbors; fix them by recoloring those neighbors red.
- If $w$'s formerly-yellow neighbors had red neighbors of their own, those need to be recolored yellow, and so on.
We can keep going this way, no problem. The (red,yellow) Kempe chain containing $w$ is the set of all vertices we end up recoloring this way: swapping red to yellow and vice versa.
Once we're done, we may or may not have fixed the problem of $v$ having red neighbors. Certainly, $w$ is no longer red: it's yellow now. But what if the Kempe chain we found contains $v$'s yellow neighbor? Then that yellow neighbor becomes red; $v$ still has neighbors of all five colors.
In this case, we are saved by arguing that not all Kempe chains can loop around in this way. For example, if the colors around $v$ go red, blue, yellow, green, purple in that order, then the (red, yellow) chain and the (blue, green) chain can't both loop around, because then the chains would end up crossing.
In other applications, we make different arguments.
This theorem does not have the kind of nice proof you're looking for.
Some of the kinds of things you could prove using a similar argument include:
- Every planar graph $G$ with a vertex $v$ of degree $\le 4$, such that $G-v$ is $4$-colorable, is also $4$-colorable.
- Every planar graph $G$ which is $4$-degenerate ($G$, and every subgraph of $G$, has a vertex of degree at most $4$) is $4$-colorable.
- If a counterexample to the four-color theorem exists, then the smallest counterexample will not have any vertices of degree $\le 4$.
In all cases, the idea is similar, and you can see this recent question and its answer to find out how. (Briefly, the step you called "rotating of coloring" is mildly more complicated.)
However, as pointed out by Michal Adamaszek in the comments, just "every planar graph with a vertex of degree $\le 4$ is $4$-colorable" is not any easier than the full four-color theorem. Suppose you prove this. Then you can start with any planar graph $G$, add a vertex $v$ of degree at most $4$ (for instance, an isolated vertex), and your theorem will tell you that $G+v$ is $4$-colorable; therefore $G$ is, too.
Best Answer
The answer is three. As for a proof:
As stated above two colours is not enough. Every square grid colouring must have either alternating colours uniformly across the grid, or somewhere there are two adjacent vertices of the same colour. In the former case then any swap of vertices will create a three-in-a-row. If there are two in a row of the same colour and we assume it is not possible to get to a three in a row configuration, then all the vertices marked X below must not be colour 1.
With only two colours this clearly creates a problem as all the X vertices must be colour 2.
To show that 3 colours suffices consider the colouring below:
The pattern can be extended to cover an infinitely large grid and it's not possible to swap to get three-in-a-row or even to get a coloured path of length three.