4
$\begingroup$

To follow on [How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable?

The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable.

I disagree with the solution given (As stated in my comment). The provided links does not proove the equivalence. It shows 1) from 4 color-theorem, how to build a 3-edge coloring for bridgeless cubic graph 2) from a 3-edge-coloring, how to build a 4 face coloring for the same graph

The theorem by Tait is much more powerful. If I can 3-edge color any cubic bridgeless planar graph, then I can 4-color ANY planar graph (not just cubic bridgeless planar).

Any idea how to prove the equivalence. I cannot find the original paper from Tait. Lots of reference but never the actual proof. The implication 4CT $\Rightarrow$ 3-edge-coloring for bridgeless planar cubic graph is easy. The other implication is the one missing : $$ \{ \forall G, \text{ cubic, planar, bridgeless}, \exists \text{ a 3-edge coloring}\}$$ $$\Rightarrow$$ $$\{\forall G, \text{ planar,} \ \exists \text{a 4-vertex-coloring}\}$$

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

Suppose we want to 4-color the vertices of a planar graph.

We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.

We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.

All planar triangulations on at least 4 vertices are 3-connected.

Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.

So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.

$\endgroup$
5
  • $\begingroup$ I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid. $\endgroup$
    – Thomas Lesgourgues
    Jan 8, 2019 at 19:39
  • $\begingroup$ The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay. $\endgroup$
    – Misha Lavrov
    Jan 8, 2019 at 20:35
  • $\begingroup$ I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks. $\endgroup$
    – Thomas Lesgourgues
    Jan 8, 2019 at 20:51
  • $\begingroup$ Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined. $\endgroup$
    – Misha Lavrov
    Jan 8, 2019 at 20:54
  • $\begingroup$ The following answer by ben explains why the 3-edge colouring must be be valid math.stackexchange.com/a/1574863/120721 $\endgroup$
    – Cyriac Antony
    May 20, 2019 at 5:21
-1
$\begingroup$

Why do you say that the explanation in the link does not prove the equivalence? You can decide to color the faces of the map OR you can color the edges of the same map. Once you have finished coloring one or the other (faces or the edges) you can switch to the other the way described in the link. The difficulty of three coloring the edges or four coloring the faces is the same. Since one has already been proved the other is proved too.

About the theorem of Tait, there is no theorem of Tait, at least not about four coloring.

The equivalency only states that for the same map (not any map) if you find one coloring (faces of edges) you can switch to the other coloring, it does not say that it is easier to find one or the other coloring. To go from one coloring to the other (related to the same map) the algorithm is described in the link. The algorithm is the proof of the equivalency.

UPDATE (25/Jan/2019): The proof should be here:

$\endgroup$
3
  • $\begingroup$ I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else? $\endgroup$
    – Misha Lavrov
    Jan 24, 2019 at 3:52
  • $\begingroup$ No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$. $\endgroup$
    – Thomas Lesgourgues
    Jan 24, 2019 at 8:56
  • $\begingroup$ And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian. $\endgroup$
    – Thomas Lesgourgues
    Jan 24, 2019 at 9:14

You must log in to answer this question.

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