Complexité de la coloration des bords dans les graphes plans

15

La coloration à 3 arêtes des graphiques cubiques est complète. Le théorème à quatre couleurs équivaut à «Chaque graphique cubique sans pont plan est colorable sur 3 bords».NP

Quelle est la complexité de la coloration à 3 arêtes des graphiques planaires cubiques?

De plus, il est conjecturé que la coloration edge est dure pour les graphes planaires avec un degré maximum {4,5}.ΔNPΔ∈

Des progrès ont-ils été réalisés pour résoudre cette conjecture?

Marek Chrobak et Takao Nishizeki. Amélioration des algorithmes de coloration des bords pour les graphes planaires. Journal of Algorithms, 11: 102-116, 1990

cc.complexity-theory graph-theory np-hardness graph-colouring Mohammad Al-Turkistany
la source
La ligne 2 du tableau 1 dans dx.doi.org/10.1007/s00453-007-9044-3 ne signifie-t- elle pas que la «coloration à 3 arêtes des graphiques planaires cubiques» est polynomialement résoluble?
Oleksandr Bondarenko
L'entrée du tableau fait référence au papier Robertson, Sanders, Seymour et Thomas Four Coloring qui traite des graphes planaires cubiques sans pont .
Mohammad Al-Turkistany
+1 grande question, j'ai une question similaire, mais plus pratique ...
draks ...
Salut, savez-vous s'il y a des progrès pour les colorations à 3 bords sur les graphiques cubiques sur un double tore ?
draks ...

Réponses:

15

Chaque graphique cubique planaire sans pont peut être coloré sur 3 bords en temps quadratique, car cette tâche équivaut à colorier en quatre un graphique planaire, ce qui peut être fait en temps quadratique. (Voir Robertson, Sanders, Seymour et Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDIT: Comme le souligne Mathieu, les graphiques cubiques avec des ponts ne sont jamais colorables sur 3 bords.

Emil
la source
5
Les graphiques cubiques avec un pont ne sont jamais colorables sur 3 bords. Cela découle du "Parité Lemme" par exemple voir la remarque sous Lemma 2.1 dans combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Colin McQuillan
1
Pour être précis, l'équivalence entre la coloration à arêtes et la coloration à 4 couleurs ne concerne que les graphes plans cubiques sans pont . 34
Mathieu Chapelle
@Emil, je ne vois pas comment cela impliquerait que les graphes PLANAIRES cubiques avec des ponts ne soient jamais colorables sur 3 bords.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany Étant donné deux couleurs a et b dans une coloration des bords d d'un graphique d-régulier (d> = 2), le sous-graphique induit par les bords colorés a ou b est une union disjointe de cycles pairs. De là découle le lemme de parité: si X est un sous-ensemble non vide propre de V (G) et F est la coupe induite par X, alors pour toutes les couleurs a et b, la parité du nombre d'arêtes de X colorées a est égale à la parité du nombre d'arêtes de X colorées b. Ergo, tout graphe d-régulier (d> = 2) avec un pont ne peut pas être coloré par le bord d, qu'il soit plan ou non.
Leandro Zatesko
5

La coloration à 3 arêtes des graphiques sans triangle avec un degré maximum 3 est également NP-complète, voir 10.1016 / S0096-3003 (96) 00021-5.

Diamantis Koreas
la source