<p>4CT is equivalent to:</p>

<ul>
<li>Coloring a hypergraph induced by a finite family of discs (not necessarily interior disjoint but also discs that might have arbitrary overlaps) with at most four colors $[1]$.</li>
<li>The proposition that every planar triangulation with more than three vertices is the union of two connected bipartite graphs, each with no isthmus $[2]$.</li>
<li>A combinatorial problem about the three-dimensional vector cross product algebra $[3]$.</li>
<li>The proposition that the grammar G is totally ambiguous $[4]$.</li>
<li>For any positive integer $n$, there exists at least a signable path joining two permutations of $S_n$.</li>
<li><p>An algebraic equivalent of the four-color theorem is presented. The equivalent is the assertion of non-membership of a family of polynomials in a family of polynomial ideals over a particular finite field $[6]$.</p>

<ol>
<li>Smorodinsky S. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.1554&amp;rep=rep1&amp;type=pdf">On the chromatic number of geometric hypergraphs</a>.</li>
<li>Mabry R. <a href="http://sun.cs.lsus.edu/~rmabry/math/rmabry/bica/4color.pdf">Bipartite Graphs and the Four-Color Theorem</a>.</li>
<li>Kauffman L.H. <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WHT-4D8DRHP-3D&amp;_user=10&amp;_coverDate=04/30/1990&amp;_rdoc=1&amp;_fmt=high&amp;_orig=gateway&amp;_origin=gateway&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=ede6a2d15f726218d76b941857fa8fdc&amp;searchtype=a">Map coloring and the vector cross product</a>.</li>
<li>Cooper B. J. et al. <a href="http://arxiv.org/abs/1006.1324">Toward a language theoretic proof of the four color theorem</a>.</li>
<li>Eliahou S. et al. <a href="http://arxiv.org/abs/math/0606726">Signed permutations and the four color theorem</a>.</li>
<li>Howard L. <a href="http://comet.lehman.cuny.edu/fitting/fourcolor/fourcolor.html">An Algebraic Reformulation of the Four Color Theorem</a>.</li>
</ol></li>
</ul>

CC BY-SA 3.0
2011-03-29T18:13:11.997Z
2012-12-30T21:32:55.113Z
2012-12-30T21:32:55.113Z
Oleksandr Bondarenko
<p>Another <a href="http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf">mechanical verification</a> of the 4-colour theorem has been done by <a href="http://research.microsoft.com/en-us/people/gonthier/">George Gonthier</a> at Microsoft Research Cambridge. The difference with his proof is that the entire theorem has been stated and mechanically verified using the Coq proof assistant, whereas the other proofs contain only the kernel calculation written in Assembly Language and C, and thus have a risk of being buggy. Gonthier's proof covers both the calculational aspects and the logical ones in just 60,000 lines of Coq.</p>

CC BY-SA 2.5
2011-03-26T08:14:58.223Z
2011-03-26T08:42:40.837Z
2011-03-26T08:42:40.837Z
Dave Clarke
<p>I have talked about this on my blog and our insight is: for example Tait's condition can be weaken to there is a coloring that has at most o(n) errors. See here: <a href="http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/">http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/</a></p>

CC BY-SA 3.0
2011-05-10T14:47:43.897Z
Really cool! Thanks for this reformulation!
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-05-10T13:34:20.373Z
2011-05-10T13:34:20.373Z
dick lipton
<p>Look at T. Saaty, Thirteen colorful variations on Guthrie's 4-color conjecture, American Math. Monthly, 79 (1972) 2-43 for many examples.</p>

<p>Also, in David Barnette's book Map Coloring, Polyhedra, and the Four-Color Problem, MAA, Dolciani Series, Volume 8, 1983 many examples are given. One particularly interesting result in Barnete's book is: If it is always possible to truncate vertices of a convex polyhedron so as to  to produce a 3-valent convex polyhedron so that the number of sides of each face is a multiple of three, it implies the truth of the four color conjecture. </p>

CC BY-SA 2.5
2011-03-26T02:51:50.780Z
2011-03-26T02:51:50.780Z
Joseph Malkevitch
<p>The <a href="http://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29">Hadwiger conjecture</a>.</p>

CC BY-SA 2.5
2011-03-26T02:42:50.120Z
2011-03-26T02:42:50.120Z
Colin McQuillan
<p>In the paper <a href="http://www.sciencedirect.com/science/article/pii/0095895674900409">Absolute Planar Retracts and the Four Color Conjecture</a>,
Pavol Hell proved several equivalente formulations for the 4CT. One of
them reads as follows:</p>

<blockquote>
  <p>Every planar graph is 4-colorable (The 4CT) iff there exists an absolute
  planar retract.</p>
</blockquote>

<p>(A subgraph $H$ of a graph $G$ is a retract of $G$ if there exists a
homomorphism $r: V(G)\to V(H)$ such that $r(v)=v$ for all
$v\in V(H)$. An absolute planar retract is a planar graph which is a
retract of any planar graph of which it is a subgraph.)</p>

CC BY-SA 3.0
2013-04-17T09:45:35.620Z
2013-04-17T09:45:35.620Z
Peng O
<p>Dror Bar-Natan's paper &quot;Lie Algebras and the Four Color Theorem&quot; (Combinatorica 17-1 (1997) 43-52, last updated October 1999, <a href="https://arxiv.org/abs/q-alg/9606016" rel="nofollow noreferrer">arXiv:q-alg/9606016</a>) contains an appealing statement about Lie algebras that is equivalent to the Four Color Theorem. The notions appearing in the statement also appear in the theory of finite-type invariants of knots (Vassiliev invariants) and 3-manifolds.</p>

CC BY-SA 4.0
2012-12-29T18:13:00.067Z
2022-05-29T17:29:27.457Z
2022-05-29T17:29:27.457Z
Gil Kalai
<p>Every bridgeless cubic planar graph is 3-edge-colourable.  (This is equivalent to 4CT, due to Tait.)</p>

CC BY-SA 3.0
2011-03-26T01:22:09.127Z
2011-04-10T15:21:21.843Z
2011-04-10T15:21:21.843Z
Andrew D. King
<p>Proposition 2.4 in this paper <a href="http://www.sciencedirect.com/science/article/pii/0012365X9500109A#">http://www.sciencedirect.com/science/article/pii/0012365X9500109A#</a> gives another formulation for the 4CT.</p>

<p><strong>Edit:</strong> For a given graph $G$, the graph $\Delta(G)$ has the edges of $G$ as its vertices; two edges of $G$ are adjacent in $\Delta(G)$ if they span a triangle in $G$. Then the 4CT can be stated as follows: For every planar graph $G$, the chromatic number of $\Delta(G)$ equals to the clique number of $\Delta(G)$.</p>

<p>I forgot to mention that Albertson and Collins previously proved in the paper<br>
<a href="http://www.sciencedirect.com/science/article/pii/0095895684900352">http://www.sciencedirect.com/science/article/pii/0095895684900352</a> 
the following similar fact: Given a graph $G$, let $K(G)$ denote the 
graph whose vertices are the edges of $G$. Two vertices of $K(G)$ are 
adjacent if the corresponding edges in $G$ are contained in a clique.<br>
Then the 4CT is equivalent to: For any planar graph $G$, the chromatic 
number and the clique number of $K(G)$ are equal.</p>

CC BY-SA 3.0
2012-12-31T05:22:50.007Z
Can you describe it here, for those of us who don't have access (or like me are too lazy to turn on the VPN to get access)?
David Eppstein
CC BY-SA 3.0
2012-12-30T15:11:36.733Z
2013-01-15T08:33:15.997Z
2013-01-15T08:33:15.997Z
vb le
<p>The high-level description of the automated proof by Gonthier is worth reading, if you are looking for more insight.</p>

<p>Yuri Matiyasevich studied several probabilistic restatements of the Four Colour Theorem, involving positive correlations between two notions of similarity between colourings.  His proofs of equivalence rely on an associated graph polynomial, which provides another likely pointer to conjectures that imply the theorem.</p>

<ul>
<li>Georges Gonthier, <a href="http://www.ams.org/notices/200811/tx081101382p.pdf"><em>Formal Proof—The Four-Color Theorem</em></a>, Notices of the American Mathematical Society <strong>55</strong>(11) 1382–1393, 2008.</li>
<li>Yuri Matiyasevich, <a href="http://logic.pdmi.ras.ru/~yumat/Journal/prob4cc1/prob4cc1.pdf.gz"><em>One Probabilistic Equivalent of the Four Color Conjecture</em></a>, translation of paper in Teoriya Veroyatnostei i ee Primeneniya <strong>48</strong> 411–416, 2003.</li>
<li>Yuri Matiyasevich, <a href="http://dx.doi.org/10.1002/jgt.10178"><em>Some Probabilistic Restatements of the Four Color Conjecture</em></a>, Journal of Graph Theory <strong>46</strong> 167–179, 2004. (<a href="http://logic.pdmi.ras.ru/~yumat/Journal/prob4cc/prob4cc.pdf.gz">preprint</a>)</li>
</ul>

CC BY-SA 2.5
2011-03-30T04:51:03.173Z
2011-03-30T04:51:03.173Z
András Salamon
<p>I just read in a paper of Chalopin and Gonçalves (STOC '09) the following conjecture of West:</p>

<blockquote>
  <p>Every planar graph is the intersection graph of segments in the plane using only four directions.</p>
</blockquote>

<p>Since parallel segments form an independent set in such a representation, this conjecture implies the 4CT, but perhaps is even stronger.</p>

<p>The reference: West, <em>Open problems</em>. SIAM J Discrete Math Newsletter, 2(1):10-12, 1991.</p>

CC BY-SA 3.0
2011-04-14T13:09:48.297Z
2011-04-14T15:33:10.653Z
2011-04-14T15:33:10.653Z
RJK
<p>A <em>snark</em> is a connected, bridgeless cubic graph that is not 3-edge-colorable. Following wikipedia, the <a href="http://en.wikipedia.org/wiki/Snark_%28graph_theory%29">snark conjecture</a>, generalizing the 4CT, is as follows: </p>

<blockquote>
  <p>Every snark has a subgraph that can be formed from the Petersen graph by subdividing some of its edges.</p>
</blockquote>

<p>Again according to wikipedia, a proof of this conjecture was announced in 2001 by Robertson, Sanders, Seymour and Thomas. </p>

CC BY-SA 3.0
2011-04-29T01:10:55.817Z
Snark theorem doesn't seem to imply 4CT, right?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-05-03T06:34:04.520Z
It does in fact imply the 4CT: Every subdivision of the Petersen graph is clearly nonplanar, so the snark conjecture implies the following reformulation of the 4CT (due to Tait): Every snark is nonplanar.
Hermann Gruber
CC BY-SA 3.0
2011-05-04T05:19:08.170Z
Ah, now I see where my problem is. The proof of the snark theorem is again a computer-aided proof. I'm under the impression that there's no human verifiable proof to the 4CT, and misunderstood your answer. Thanks!!
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-04-28T22:42:40.737Z
2011-05-04T05:20:58.810Z
2011-05-04T05:20:58.810Z
Hermann Gruber
<p>"The Face Labeling Of Maximal Planar Graphs" is the title of my old paper which has been published recently in which I have transformed 4 coloring of maximal planar graphs into consistency of face labeling. Link to the paper is <a href="http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf" rel="nofollow">http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf</a></p>

CC BY-SA 2.5
2011-04-04T13:40:28.497Z
2011-04-04T13:40:28.497Z
Cahit
<p>Garry Bowlin and Matthew G. Brin's paper "Coloring Planar Graphs via Colored Paths in the Associahedra", last revised 12 May 2013, <a href="http://arxiv.org/abs/1301.3984" rel="nofollow">arXiv:1301.3984 math.CO</a> contains the following conjecture on page 26:</p>

<blockquote>
  <p>Conjecture 6.4. For every pair of ﬁnite, binary trees (D, R) with the same number
  of leaves, there is a sign assignment of D and a word w of rotation symbols valid
  for D so that Dw = R.</p>
</blockquote>

<p>It is stated that conjecture 6.4 following from previous propositions and theorems in the paper is equivalent to 4CT.</p>

CC BY-SA 3.0
2013-08-28T03:34:06.960Z
2013-08-28T03:34:06.960Z
David Clark
<p>As  </p>

<p>L.H. Kauffman, <a href="http://www.math.uic.edu/~kauffman/MapReform.pdf" rel="nofollow">Reformulating the map color theorem</a>, Discrete Mathematics 302 (2005) 145–172</p>

<p>points out, the <em>Primality Principle</em> due to G. Spencer-Brown as well as the <em>Eliahou–Kryuchkov conjecture</em> are equivalent reformulations of the FCT.</p>

<ul>
<li>S. Eliahou, Signed diagonal flips and the four color theorem, European J. Combin. 20 (1999) 641–646.</li>
<li>S. I. Kryuchkov, The four color theorem and trees, I. V. Kruchatov, Institute of Atomic Energy, Moscow, 1992, IAE-5537/1.</li>
<li>G. Spencer-Brown, Laws of Form, Gesetze der Form, Bohmeier Verlag, 1997.</li>
</ul>

CC BY-SA 3.0
2011-04-28T22:21:17.313Z
2011-04-28T22:21:17.313Z
Hermann Gruber
<p>A <em>k</em>-flow on an undirected graph <em>G</em> is a directed graph derived by replacing each edge in <em>G</em> with an arc and assigning it an integer between <em>-k</em> and <em>k</em>, exclusive, such that, for each vertex in G, the sum of the integers assigned to arcs pointing into that vertex is equal to the sum of the integers assigned to arcs pointing out. A NWZ (nowhere zero) <em>k</em>-flow is a <em>k</em>-flow in which no arc has been assigned the number 0.</p>

<p>For any planar graph <em>G</em>, the dual of <em>G</em> is the graph that contains one vertex for each face in a planar embedding of <em>G</em>, and two vertices in a dual share one edge connecting them for every edge that the corresponding faces in <em>G</em> share between them in their boundaries. According to Tutte's Flow-Colouring Duality Theorem, a planar graph with no isthmus (i.e. edge whose deletion would increase the number of components) has a NWZ <em>k</em>-flow if and only if its dual is <em>k</em>-colourable. In other words, a planar graph is 4-colourable if and only if its dual has a NWZ 4-flow.</p>

<p>Note that 4CT requires the planar graph in question to have no loops (edges connecting any vertex to itself) because any graph with a loop cannot be vertex-coloured with any set of colours, since any vertex with a loop would therefore be adjacent to a vertex of the same colour, regardless of its colour.</p>

CC BY-SA 3.0
2014-08-06T03:42:35.443Z
2014-08-06T03:42:35.443Z
Jordan Longstaff
<p>I am working on this:</p>

<p>If you can prove the theorem for rectangular maps, that are maps made from overlapping sheets of paper, you have also proved the 4ct. In addition, only maps with faces having all 5 edges or more can be considered in the search.</p>

<p>See <a href="http://4coloring.wordpress.com/" rel="nofollow">http://4coloring.wordpress.com/</a> for details.</p>

CC BY-SA 2.5
2011-03-28T21:49:26.703Z
2011-03-28T21:49:26.703Z
Mario Stefanutti
<p><a href="http://en.wikipedia.org/wiki/Four_color_theorem">Four Color Theorem</a> (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-assisted and quite intimidating.</p>

<p>There are several conjectures in graph theory that imply 4CT. Resolution of these conjectures probably requires a better understanding of the proofs of 4CT. Here is one such conjecture :</p>

<p><strong>Conjecture</strong> : Let $G$ be a planar graph, let $C$ be a set of colors and $f : C \rightarrow C$ a fixed-point free involution. Let $L = (L_v : v \in V(G))$ be such that </p>

<ul>
<li>$|L_v| \geq 4$ for all $v \in V$ and</li>
<li>if $\alpha \in L_v$ then $f(\alpha) \in L_v$ for all $v \in V$, for all $\alpha \in C$.</li>
</ul>

<p>Then there exists an $L$-coloring of the graph $G$.</p>

<p>If you know such conjectures implying 4CT, please list them one in each answer. I could not find a comprehensive list of such conjectures.</p>

CC BY-SA 3.0
2013-04-17T10:02:15.887Z
"They didn't have a bug in Coq and no cosmic rays flew through their computer when they checked the 4 color theorem" is one such conjecture.
Andrej Bauer
CC BY-SA 3.0
2014-08-06T16:33:33.643Z
ref for the stated conjecture?
vzn
CC BY-SA 3.0
2015-09-10T14:26:24.297Z
A related question is asked over at mathoverflow: http://mathoverflow.net/q/189097/1345
Ian Agol
<graph-theory><co.combinatorics><big-list><graph-colouring>
Conjectures implying Four Color Theorem
Shiva Kintali
# Conjectures implying Four Color Theorem

(Asked by: username_0 on 2011-03-26)

[Four Color Theorem](http://en.wikipedia.org/wiki/Four_color_theorem) (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-assisted and quite intimidating.

There are several conjectures in graph theory that imply 4CT. Resolution of these conjectures probably requires a better understanding of the proofs of 4CT. Here is one such conjecture :

**Conjecture** : Let $G$ be a planar graph, let $C$ be a set of colors and $f : C \rightarrow C$ a fixed-point free involution. Let $L = (L\_v : v \in V(G))$ be such that

* $|L\_v| \geq 4$ for all $v \in V$ and
* if $\alpha \in L\_v$ then $f(\alpha) \in L\_v$ for all $v \in V$, for all $\alpha \in C$.

Then there exists an $L$-coloring of the graph $G$.

If you know such conjectures implying 4CT, please list them one in each answer. I could not find a comprehensive list of such conjectures.

**Tags:** graph-theory, co.combinatorics, big-list, graph-colouring

> **Comments:**
> **username_1**: "They didn't have a bug in Coq and no cosmic rays flew through their computer when they checked the 4 color theorem" is one such conjecture.  
> **username_2**: ref for the stated conjecture?  
> **username_3**: A related question is asked over at mathoverflow: http://mathoverflow.net/q/189097/1345  

---

## 17 answers

### Answer by username_4 on 2011-03-29. Score: 31

4CT is equivalent to:

* Coloring a hypergraph induced by a finite family of discs (not necessarily interior disjoint but also discs that might have arbitrary overlaps) with at most four colors $[1]$.
* The proposition that every planar triangulation with more than three vertices is the union of two connected bipartite graphs, each with no isthmus $[2]$.
* A combinatorial problem about the three-dimensional vector cross product algebra $[3]$.
* The proposition that the grammar G is totally ambiguous $[4]$.
* For any positive integer $n$, there exists at least a signable path joining two permutations of $S\_n$.
* An algebraic equivalent of the four-color theorem is presented. The equivalent is the assertion of non-membership of a family of polynomials in a family of polynomial ideals over a particular finite field $[6]$.

  1. Smorodinsky S. [On the chromatic number of geometric hypergraphs](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.1554&rep=rep1&type=pdf).
  2. Mabry R. [Bipartite Graphs and the Four-Color Theorem](http://sun.cs.lsus.edu/~rmabry/math/rmabry/bica/4color.pdf).
  3. Kauffman L.H. [Map coloring and the vector cross product](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHT-4D8DRHP-3D&_user=10&_coverDate=04/30/1990&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=ede6a2d15f726218d76b941857fa8fdc&searchtype=a).
  4. Cooper B. J. et al. [Toward a language theoretic proof of the four color theorem](http://arxiv.org/abs/1006.1324).
  5. Eliahou S. et al. [Signed permutations and the four color theorem](http://arxiv.org/abs/math/0606726).
  6. Howard L. [An Algebraic Reformulation of the Four Color Theorem](http://comet.lehman.cuny.edu/fitting/fourcolor/fourcolor.html).


---

### Answer by username_5 on 2011-03-26. Score: 20

Another [mechanical verification](http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf) of the 4-colour theorem has been done by [George Gonthier](http://research.microsoft.com/en-us/people/gonthier/) at Microsoft Research Cambridge. The difference with his proof is that the entire theorem has been stated and mechanically verified using the Coq proof assistant, whereas the other proofs contain only the kernel calculation written in Assembly Language and C, and thus have a risk of being buggy. Gonthier's proof covers both the calculational aspects and the logical ones in just 60,000 lines of Coq.


---

### Answer by username_6 on 2011-05-10. Score: 19

I have talked about this on my blog and our insight is: for example Tait's condition can be weaken to there is a coloring that has at most o(n) errors. See here: <http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/>

> **Comments:**
> **username_7**: Really cool! Thanks for this reformulation!  

---

### Answer by username_8 on 2011-03-26. Score: 18

Look at T. Saaty, Thirteen colorful variations on Guthrie's 4-color conjecture, American Math. Monthly, 79 (1972) 2-43 for many examples.

Also, in David Barnette's book Map Coloring, Polyhedra, and the Four-Color Problem, MAA, Dolciani Series, Volume 8, 1983 many examples are given. One particularly interesting result in Barnete's book is: If it is always possible to truncate vertices of a convex polyhedron so as to to produce a 3-valent convex polyhedron so that the number of sides of each face is a multiple of three, it implies the truth of the four color conjecture.


---

### Answer by username_9 on 2011-03-26. Score: 17

The [Hadwiger conjecture](http://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29).


---

### Answer by username_10 on 2013-04-17. Score: 12

In the paper [Absolute Planar Retracts and the Four Color Conjecture](http://www.sciencedirect.com/science/article/pii/0095895674900409),
Pavol Hell proved several equivalente formulations for the 4CT. One of
them reads as follows:

> Every planar graph is 4-colorable (The 4CT) iff there exists an absolute
> planar retract.

(A subgraph $H$ of a graph $G$ is a retract of $G$ if there exists a
homomorphism $r: V(G)\to V(H)$ such that $r(v)=v$ for all
$v\in V(H)$. An absolute planar retract is a planar graph which is a
retract of any planar graph of which it is a subgraph.)


---

### Answer by username_11 on 2012-12-29. Score: 12

Dror Bar-Natan's paper "Lie Algebras and the Four Color Theorem" (Combinatorica 17-1 (1997) 43-52, last updated October 1999, [arXiv:q-alg/9606016](https://arxiv.org/abs/q-alg/9606016)) contains an appealing statement about Lie algebras that is equivalent to the Four Color Theorem. The notions appearing in the statement also appear in the theory of finite-type invariants of knots (Vassiliev invariants) and 3-manifolds.


---

### Answer by username_12 on 2011-03-26. Score: 11

Every bridgeless cubic planar graph is 3-edge-colourable. (This is equivalent to 4CT, due to Tait.)


---

### Answer by username_13 on 2012-12-30. Score: 11

Proposition 2.4 in this paper <http://www.sciencedirect.com/science/article/pii/0012365X9500109A#> gives another formulation for the 4CT.

**Edit:** For a given graph $G$, the graph $\Delta(G)$ has the edges of $G$ as its vertices; two edges of $G$ are adjacent in $\Delta(G)$ if they span a triangle in $G$. Then the 4CT can be stated as follows: For every planar graph $G$, the chromatic number of $\Delta(G)$ equals to the clique number of $\Delta(G)$.

I forgot to mention that Albertson and Collins previously proved in the paper  
<http://www.sciencedirect.com/science/article/pii/0095895684900352>
the following similar fact: Given a graph $G$, let $K(G)$ denote the
graph whose vertices are the edges of $G$. Two vertices of $K(G)$ are
adjacent if the corresponding edges in $G$ are contained in a clique.  
Then the 4CT is equivalent to: For any planar graph $G$, the chromatic
number and the clique number of $K(G)$ are equal.

> **Comments:**
> **username_14**: Can you describe it here, for those of us who don't have access (or like me are too lazy to turn on the VPN to get access)?  

---

### Answer by username_15 on 2011-03-30. Score: 9

The high-level description of the automated proof by Gonthier is worth reading, if you are looking for more insight.

Yuri Matiyasevich studied several probabilistic restatements of the Four Colour Theorem, involving positive correlations between two notions of similarity between colourings. His proofs of equivalence rely on an associated graph polynomial, which provides another likely pointer to conjectures that imply the theorem.

* Georges Gonthier, [*Formal Proof—The Four-Color Theorem*](http://www.ams.org/notices/200811/tx081101382p.pdf), Notices of the American Mathematical Society **55**(11) 1382–1393, 2008.
* Yuri Matiyasevich, [*One Probabilistic Equivalent of the Four Color Conjecture*](http://logic.pdmi.ras.ru/~yumat/Journal/prob4cc1/prob4cc1.pdf.gz), translation of paper in Teoriya Veroyatnostei i ee Primeneniya **48** 411–416, 2003.
* Yuri Matiyasevich, [*Some Probabilistic Restatements of the Four Color Conjecture*](http://dx.doi.org/10.1002/jgt.10178), Journal of Graph Theory **46** 167–179, 2004. ([preprint](http://logic.pdmi.ras.ru/~yumat/Journal/prob4cc/prob4cc.pdf.gz))


---

### Answer by username_16 on 2011-04-14. Score: 8

I just read in a paper of Chalopin and Gonçalves (STOC '09) the following conjecture of West:

> Every planar graph is the intersection graph of segments in the plane using only four directions.

Since parallel segments form an independent set in such a representation, this conjecture implies the 4CT, but perhaps is even stronger.

The reference: West, *Open problems*. SIAM J Discrete Math Newsletter, 2(1):10-12, 1991.


---

### Answer by username_17 on 2011-04-28. Score: 6

A *snark* is a connected, bridgeless cubic graph that is not 3-edge-colorable. Following wikipedia, the [snark conjecture](http://en.wikipedia.org/wiki/Snark_%28graph_theory%29), generalizing the 4CT, is as follows:

> Every snark has a subgraph that can be formed from the Petersen graph by subdividing some of its edges.

Again according to wikipedia, a proof of this conjecture was announced in 2001 by Robertson, Sanders, Seymour and Thomas.

> **Comments:**
> **username_7**: Snark theorem doesn't seem to imply 4CT, right?  
> **username_17**: It does in fact imply the 4CT: Every subdivision of the Petersen graph is clearly nonplanar, so the snark conjecture implies the following reformulation of the 4CT (due to Tait): Every snark is nonplanar.  
> **username_7**: Ah, now I see where my problem is. The proof of the snark theorem is again a computer-aided proof. I'm under the impression that there's no human verifiable proof to the 4CT, and misunderstood your answer. Thanks!!  

---

### Answer by username_18 on 2011-04-04. Score: 3

"The Face Labeling Of Maximal Planar Graphs" is the title of my old paper which has been published recently in which I have transformed 4 coloring of maximal planar graphs into consistency of face labeling. Link to the paper is <http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf>


---

### Answer by username_19 on 2013-08-28. Score: 3

Garry Bowlin and Matthew G. Brin's paper "Coloring Planar Graphs via Colored Paths in the Associahedra", last revised 12 May 2013, [arXiv:1301.3984 math.CO](http://arxiv.org/abs/1301.3984) contains the following conjecture on page 26:

> Conjecture 6.4. For every pair of ﬁnite, binary trees (D, R) with the same number
> of leaves, there is a sign assignment of D and a word w of rotation symbols valid
> for D so that Dw = R.

It is stated that conjecture 6.4 following from previous propositions and theorems in the paper is equivalent to 4CT.


---

### Answer by username_17 on 2011-04-28. Score: 3

As

L.H. Kauffman, [Reformulating the map color theorem](http://www.math.uic.edu/~kauffman/MapReform.pdf), Discrete Mathematics 302 (2005) 145–172

points out, the *Primality Principle* due to G. Spencer-Brown as well as the *Eliahou–Kryuchkov conjecture* are equivalent reformulations of the FCT.

* S. Eliahou, Signed diagonal flips and the four color theorem, European J. Combin. 20 (1999) 641–646.
* S. I. Kryuchkov, The four color theorem and trees, I. V. Kruchatov, Institute of Atomic Energy, Moscow, 1992, IAE-5537/1.
* G. Spencer-Brown, Laws of Form, Gesetze der Form, Bohmeier Verlag, 1997.


---

### Answer by username_20 on 2014-08-06. Score: 1

A *k*-flow on an undirected graph *G* is a directed graph derived by replacing each edge in *G* with an arc and assigning it an integer between *-k* and *k*, exclusive, such that, for each vertex in G, the sum of the integers assigned to arcs pointing into that vertex is equal to the sum of the integers assigned to arcs pointing out. A NWZ (nowhere zero) *k*-flow is a *k*-flow in which no arc has been assigned the number 0.

For any planar graph *G*, the dual of *G* is the graph that contains one vertex for each face in a planar embedding of *G*, and two vertices in a dual share one edge connecting them for every edge that the corresponding faces in *G* share between them in their boundaries. According to Tutte's Flow-Colouring Duality Theorem, a planar graph with no isthmus (i.e. edge whose deletion would increase the number of components) has a NWZ *k*-flow if and only if its dual is *k*-colourable. In other words, a planar graph is 4-colourable if and only if its dual has a NWZ 4-flow.

Note that 4CT requires the planar graph in question to have no loops (edges connecting any vertex to itself) because any graph with a loop cannot be vertex-coloured with any set of colours, since any vertex with a loop would therefore be adjacent to a vertex of the same colour, regardless of its colour.


---

### Answer by username_21 on 2011-03-28. Score: 0

I am working on this:

If you can prove the theorem for rectangular maps, that are maps made from overlapping sheets of paper, you have also proved the 4ct. In addition, only maps with faces having all 5 edges or more can be considered in the search.

See <http://4coloring.wordpress.com/> for details.


---

