Conjectures impliquant le théorème des quatre couleurs

38

Le théorème des quatre couleurs (4CT) stipule que chaque graphe planaire peut être coloré en quatre. [Appel, Haken 1976] et [Robertson, Sanders, Seymour, Thomas 1997] ont donné deux preuves. Ces deux preuves sont assistées par ordinateur et assez intimidantes.

Il existe plusieurs conjectures en théorie des graphes qui impliquent 4CT. La résolution de ces conjectures nécessite probablement une meilleure compréhension des preuves de 4CT. Voici une de ces conjectures:

Conjecture : Soit un graphe planaire, soit un ensemble de couleurs et une involution libre à virgule fixe. Soit tel queC f : C C L = ( L v : v V ( G ) )gCF:CCL=(Lv:vV(g))

  • |Lv|4 pour tous etvV
  • si alors f (\ alpha) \ in L_V pour tous les v \ in V , pour tout \ alpha \ in C . f ( α ) L v v V α CαLvf(α)LvvVαC

Ensuite , il existe un L -coloration du graphe g .

Si vous connaissez de telles hypothèses impliquant 4CT, veuillez les énumérer une dans chaque réponse. Je n'ai pas pu trouver une liste complète de telles conjectures.

Shiva Kintali
la source
6
"Ils n'avaient pas de bogue dans Coq et aucun rayon cosmique ne traversait leur ordinateur lorsqu'ils vérifiaient le théorème des 4 couleurs", est l'une de ces conjectures.
Andrej Bauer
réf pour la conjecture énoncée?
vzn
Une question connexe est posée à mathoverflow: mathoverflow.net/q/189097/1345
Ian Agol

Réponses:

28

4CT équivaut à:

Oleksandr Bondarenko
la source
20

Une autre vérification mécanique du théorème des 4 couleurs a été effectuée par George Gonthier de Microsoft Research Cambridge. La différence avec sa preuve est que tout le théorème a été énoncé et vérifié mécaniquement à l'aide de l'assistant de preuves Coq, alors que les autres preuves ne contiennent que le calcul du noyau écrit en langage d'assemblage et en langage C, et risquent donc d'être gênants. La preuve de Gonthier couvre à la fois les aspects de calcul et les aspects logiques dans seulement 60 000 lignes de Coq.

Dave Clarke
la source
18

Regardez T. Saaty, Treize variations colorées de la conjecture à quatre couleurs de Guthrie, American Math. Monthly, 79 (1972) 2-43 pour de nombreux exemples.

De plus, dans le livre de David Barnette, Map Colouring, Polyhedra et le problème des quatre couleurs, MAA, Dolciani Series, volume 8, 1983, de nombreux exemples sont donnés. Un résultat particulièrement intéressant dans le livre de Barnete est le suivant: s'il est toujours possible de tronquer les sommets d'un polyèdre convexe de manière à produire un polyèdre convexe à 3 valences de sorte que le nombre de côtés de chaque face soit un multiple de trois, cela implique la vérité de la conjecture à quatre couleurs.

Joseph Malkevitch
la source
12

Dans le document Absolute Planar Retracts et la conjecture à quatre couleurs , Pavol Hell a prouvé plusieurs formulations équivalentes pour le 4CT. L'un d'eux se lit comme suit:

Chaque graphe planaire est quadrichromique (The 4CT) ssi il existe un retrait absolu planaire.

(Un sous-graphe d’un graphe G est un retrait de G s’il existe un homomorphisme r : V ( G ) V ( H ) tel que r ( v ) = v pour tout v V ( H ) . Un retrait planaire absolu est un graphe planaire qui est un retrait de tout graphe planaire dont il est un sous-graphe.)HGGr:V(G)V(H)r(v)=vvV(H)

Peng O
la source
11

Chaque graphe planaire cubique sans pontage est colorable en 3 arêtes. (Cela équivaut à 4CT, à cause de Tait.)

Andrew D. King
la source
11

L'article de Dror Bar-Natan intitulé "Algèbres de Lie et le théorème des quatre couleurs" (Combinatorica 17-1 (1997) 43-52, dernière mise à jour en octobre 1999, arXiv: q-alg / 9606016 ) contient une déclaration attrayante sur les algèbres de Lie qui est équivalente à le théorème des quatre couleurs. Les notions apparaissant dans la déclaration apparaissent également dans la théorie des invariants de type fini des noeuds (invariants de Vassiliev) et des variétés de 3.

Gil Kalai
la source
11

La proposition 2.4 dans cet article http://www.sciencedirect.com/science/article/pii/0012365X9500109A# donne une autre formulation pour le 4CT.

Edit: pour un graphe donnég, le graphique Δ(g) a les bords de gcomme ses sommets; deux bords deg sont adjacents dans Δ(g) s'ils s'étendent sur un triangle g. Ensuite, le 4CT peut être énoncé comme suit: Pour chaque graphe planaireg, le nombre chromatique de Δ(g) est égal au nombre de cliques de Δ(g).

J'ai oublié de mentionner qu'Albertson et Collins avaient déjà fait la preuve dans l'article
http://www.sciencedirect.com/science/article/pii/0095895684900352 du fait similaire suivant: Compte tenu d'un graphiqueg, laisser 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.

vb le
la source
4
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
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.

András Salamon
la source
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.

RJK
la source
6

A snark is a connected, bridgeless cubic graph that is not 3-edge-colorable. Following wikipedia, the snark conjecture, 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.

Hermann Gruber
la source
Snark theorem doesn't seem to imply 4CT, right?
Hsien-Chih Chang 張顯之
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
1
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 張顯之
3

As

L.H. Kauffman, Reformulating the map color theorem, 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.
Hermann Gruber
la source
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 contains the following conjecture on page 26:

Conjecture 6.4. For every pair of finite, 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.

David Clark
la source
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.

Jordan Longstaff
la source
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.

Mario Stefanutti
la source