11
$\begingroup$

The five color theorem for planar maps is considerably easier to prove than the four color theorem. The essential part of the proof is the Kempe-Heawood swap: given coloring of a map, choose two countries with common border and swap their colors in the connected component of the countries of the two colors. The swap obviously produces new coloring of the map. The question is: are all four (or five) colorings of a planar graph connected by a sequence of swaps?

This problem somewhat resembles solving the Rubik's cube.

The question can be generalized to n colorings of an arbitrary graph.

$\endgroup$
12
  • 1
    $\begingroup$ there are isolated islands where some internal countries colors may be swapped but the connection colors are often mandatories to fullfill the 4 colors conditions for complex maps. What is exactly the relation to the 5 colors ? is the question on 4 or 5 ? $\endgroup$
    – user354674
    Commented Sep 2, 2016 at 0:35
  • $\begingroup$ @igael the swap is used in the proof of the five color theorem for planar maps and, I believe, can be used for higher genus too... The problem is interesting to me for planar maps with four-colorings or general graphs with their chromatic number of colors... $\endgroup$
    – DVD
    Commented Sep 3, 2016 at 19:02
  • $\begingroup$ You need an answer related to the Kempe-Heawood swap. I worked on a script to color a fractal map without the knowledge of this formalism... Sorry. But, if the problem becomes more precise with a partial answer and if I know something, I'll submit it $\endgroup$
    – user354674
    Commented Sep 3, 2016 at 19:14
  • $\begingroup$ In particular: are any two four-colorings of a planar map connected by the swap? $\endgroup$
    – DVD
    Commented Sep 7, 2016 at 0:09
  • 1
    $\begingroup$ To prove that the set of 4-colorings is non-empty, is itself non-trivial, so I am not sure how this can be answered in a few days, bounty notwithstanding. And what is the quotient w.r.t an equivalence relation? $\endgroup$
    – Aravind
    Commented Sep 8, 2016 at 7:30

1 Answer 1

5
+100
$\begingroup$

I think I have solved the problem for all numbers of colors $n\ne 5$.

For a graph $G$ consider the graph $G_n$, whose vertices are $n$-colorings of $G$ and whose edges are pairs of colorings that can be obtained from each other by a Kempe-Heawood swap. The question: "Is $G_n$ connected?"

We can assume that $G$ is connected itself, because for any $n$ connectedness of $G_n$ is equivalent to connectedness of $K_n$ for all components $K$ of $G$.

$n = 1$ or $2$

In the case $n=1$ we have $|G_1|\le 1$, so $G_1$ is obviously connected. In the case $n=2$ if $G_2$ is non-empty, then $G$ is a connected bipartite graph, which can be colored only in two different ways, connected by an all-vertices Kempe-Heawood swap. So when $n\le 2$ the answer is positive for all graphs, not planar only.

$n \ge 3$, non-planar case

The answer is negative and here is a counterexample, inspired by the planar case for $n=3$. Consider the graph $G$, whose vertices are the elements of $\{0,1\}\times\{0,1,\cdots,n-1\}$, and $a=(1,y_1)$ and $b=(0,y_2)$ are connected by the edge iff $y_1-y_2$ is not $0$ or $1$ modulo $n$. $(x,y_1)$ and $(x,y_2)$ are connected by the edge for any $x,y_1,y_2$. There is a coloring with colors $0,1,\cdots,n-1$, which just color the vertex $(x,y)$ into $y$. Also there is another coloring such that $(0,y)$ is colored into $y$ and $(1,y)$ into $y-1$ modulo $n$. We excluded exactly those edges from the full graph for this two colorings to be correct.

However, any Kempe-Heawood swap of the first given coloring just renames the two colors. Indeed, $(0,a),(1,a),(0,b),(1,b)$ are all the vertices of the colors $a$ and $b$, $(0,a)$ and $(0,b)$ are connected, $(1,a)$ and $(1,b)$ are connected, and for $a\ne b$ it cannot be the case that $a-b$ and $b-a$ are both $1$ modulo $n\ge 3$, so $(0,a),(1,a),(0,b),(1,b)$ lie in the same Kempe-Heawood chain. Therefore, any swap preserves the fact that $(0,y)$ and $(1,y)$ are of the same color, but this doesn't hold for the second given coloring. Thus, $G_n$ is not connected.

$n = 3$, planar case

For $n=3$ the construction above yields the following two colorings:

enter image description here

$n = 4$, planar case

Unfortunately, the constructed counterexample is not planar for $n\ge 4$. Nevertheless, here is a planar counterexample for $n=4$:

enter image description here

This is a projection of a cube, augmented by 6 extra edges. On the left picture the opposite vertices of the cube are of the same color. It is straightforward to verify that after any swap this property holds. However, this is not true for the right picture, thus $G_4$ is not connected for this graph.

$n=5$, planar case

I don't have a working idea how to approach it. I tried to consider the dodecahedron projection with symmetric 5-coloring (the vertices of every color form a tetrahedron), but then it's impossible to add edges in such a way that graph remains planar and for all swaps all the vertices of the swap colors lie in the same component.

$n\ge 6$, planar case

The answer is positive (okay, at least for finite graphs, I didn't thought about infinite case much), and this is pretty easy to prove by induction on number of vertices in $G$. Base $|G|=1$ is trivial. Now let us have two $n$-colorings $A$ and $B$ of the graph $G$. There is a vertex $x\in G$ with degree not greater than $5$, because $G$ is planar. Consider the graph $G-x$ and restrict both $A$ and $B$ on it. By induction hypothesis, there exists a series of swaps, sending $A$ to $B$ in $G-x$.

Let us try to perform it in the graph $G$, ignoring $x$. The only case where we can't ignore $x$ is when we are trying to swap colors $a$ and $b$, $x$ is of the color $a$ and has at least two neighbors of the color $b$, thus decreasing the number of components in a full subgraph of colors $a$ and $b$, comparing to $G-x$. However, this means, there are not greater than 4 colors among the neighbors of $x$. Therefore, there exists a color such that neither $x$, nor its neighbors are of that color. We can swap $a$ and this sixth color on the component, consisting of the vertex $x$. After that, $x$ doesn't interfere with intended swap of $a$ and $b$ anymore, and we can proceed further on $G-x$.

So we can turn $A$ into $B$ modulo vertex $x$. But the thing is, even if $x$ now is not of the same color than in $B$, we can swap the resulting color of $x$ with the color of $x$ in $B$ and obtain $B$, qed.

P.S. I hope someone will correct all mistakes in my English and remove this post scriptum.

$\endgroup$
7
  • $\begingroup$ Great answer! Can you say something about the number of connected components of $G_n$ for $n$ colorings of a non-planar graph? $\endgroup$
    – DVD
    Commented Feb 5, 2017 at 20:20
  • $\begingroup$ For the planar $n\ge 6$ case, the only fact about the planarity you use is that there are inductively vertices of the degree at most $5$? $\endgroup$
    – DVD
    Commented Feb 5, 2017 at 21:20
  • $\begingroup$ @DVD Yes, I used nothing more and in fact I don't see the ways to use planarity more essentially (for the case $n=5$). Though if it is possible to prove, then we probably should find a different way. The number of components can be exponential in number of vertices, because we can just copy graph many times, and the number of components in $G_n$ is the product of those of $K_n$ for components $K$ of $G$. Connectedness restriction on $G$ doesn't help, because we can sparsely connect components without any effect on $G_n$. $\endgroup$
    – Wolfram
    Commented Feb 6, 2017 at 0:39
  • $\begingroup$ I've got two questions about the last case: "Therefore, there exists a color such that neither $x$, nor its neighbors are of that color. We can swap $a$ and this sixth color on the component, consisting of the vertex $x$". There're no color six neighbors of $x$, so we cannot perform the switch of the colors in the connected component containing x. And for the last step, when A and B are the same colorings except x, the swap will change more than one color, so they'll not be the same? $\endgroup$
    – DVD
    Commented Feb 6, 2017 at 4:45
  • $\begingroup$ Maybe we should add another move to the swap: if a vertex doesn't have neighbors of all colors, it can be colored in the missing one? $\endgroup$
    – DVD
    Commented Feb 6, 2017 at 4:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .