Conjectures impliquant le théorème des quatre couleurs

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 ) $G$$C$$f : C \rightarrow C$$L = (L_v : v \in V(G))$

• $|L_v| \geq 4$ pour tous et$v \in V$
• si alors f (\ alpha) \ in L_V pour tous les v \ in V , pour tout \ alpha \ in C . f ( α ) ∈ L v v ∈ V α ∈ $\alpha \in L_v$$f(\alpha) \in L_v$$v \in V$$\alpha \in 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.

4CT équivaut à:

• Coloration d'un hypergraphe induit par une famille finie de disques (pas nécessairement disjoints de l'intérieur mais également des disques pouvant avoir des chevauchements arbitraires) avec au plus quatre couleurs .$[1]$
• La proposition selon laquelle chaque triangulation plane avec plus de trois sommets est l'union de deux graphes bipartites connectés, chacun sans isthme .$[2]$
• Un problème combinatoire à propos de l'algèbre de produits vectoriels tridimensionnels .$[3]$
• La proposition selon laquelle la grammaire G est totalement ambiguë .$[4]$
• Pour tout entier positif , il existe au moins un chemin signable joignant deux permutations de S n .$n$$S_n$

• Un équivalent algébrique du théorème des quatre couleurs est présenté. L'équivalent est l'affirmation de non-appartenance à une famille de polynômes dans une famille d'idéaux polynomiaux sur un corps fini particulier .$[6]$

  1. Smorodinsky S. Sur le nombre chromatique d'hypergraphes géométriques .
  2. Mabry R. Graphes bipartites et le théorème des quatre couleurs .
  3. Kauffman LH Coloration de la carte et produit vectoriel croisé .
  4. Cooper BJ et al. Vers une preuve théorique du langage du théorème des quatre couleurs .
  5. Eliahou S. et al. Les permutations signées et le théorème des quatre couleurs .
  6. Howard L. Une reformulation algébrique du théorème des quatre couleurs .

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.

J'en ai parlé sur mon blog et voici ce que nous en pensons: par exemple, l'état de Tait peut être affaibli et il existe une coloration comportant au plus o (n) erreurs. Voir ici: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/

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.

La conjecture de Hadwiger .

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.)$H$$G$$G$$r: V(G)\to V(H)$$r(v)=v$$v\in V(H)$

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

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.

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 $\Delta(G)$ a les bords de $G$comme ses sommets; deux bords de$G$ sont adjacents dans $\Delta(G)$ s'ils s'étendent sur un triangle $G$. Ensuite, le 4CT peut être énoncé comme suit: Pour chaque graphe planaire$G$, le nombre chromatique de $\Delta(G)$ est égal au nombre de cliques de $\Delta(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 graphique$G$, 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.

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, Notices of the American Mathematical Society 55(11) 1382–1393, 2008.
• Yuri Matiyasevich, One Probabilistic Equivalent of the Four Color Conjecture, translation of paper in Teoriya Veroyatnostei i ee Primeneniya 48 411–416, 2003.
• Yuri Matiyasevich, Some Probabilistic Restatements of the Four Color Conjecture, Journal of Graph Theory 46 167–179, 2004. (preprint)

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.

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.

"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

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.

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.

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.

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.