Komplexität der Kantenfärbung in ebenen Diagrammen

15

Die 3-Kanten-Färbung von kubischen Graphen ist -vollständig. Der Vier-Farben-Satz ist äquivalent zu "Alle kubischen planaren brückenlosen Graphen können mit drei Kanten eingefärbt werden".NP

Wie komplex ist das Einfärben von kubischen ebenen Graphen mit drei Kanten?

Es wird auch vermutet, dass die Kantenfärbung für ebene Graphen mit maximalem Wert {4,5} hart ist .N P Δ ∈ΔNPΔ∈

Wurden Fortschritte bei der Lösung dieser Vermutung erzielt?

Marek Chrobak und Takao Nishizeki. Verbesserte Kantenfärbealgorithmen für planare Grafiken. Journal of Algorithms, 11: 102 & ndash; 116, 1990

cc.complexity-theory graph-theory np-hardness graph-colouring Mohammad Al-Turkistany
quelle
Bedeutet Zeile 2 in Tabelle 1 in dx.doi.org/10.1007/s00453-007-9044-3 nicht , dass "3-Kanten-Färbung von kubischen ebenen Graphen" polynomiell lösbar ist?
Oleksandr Bondarenko
Der Tabelleneintrag bezieht sich auf Robertson, Sanders, Seymour und Thomas Four Coloring Paper, das sich mit kubischen planaren Graphen ohne Brücke befasst .
Mohammad Al-Turkistany
+1 tolle Frage, ich habe eine ähnliche, aber praktischer ...
draks ...
Hallo, wissen Sie, ob bei kubischen Diagrammen auf einem doppelten Torus Fortschritte bei Färbungen mit drei Kanten zu verzeichnen sind ?
Draks ...

Antworten:

15

Jeder brückenlose planare kubische Graph kann in quadratischer Zeit dreikantig gefärbt werden, da diese Aufgabe der vierfachen Färbung eines planaren Graphen entspricht, die in quadratischer Zeit durchgeführt werden kann. (Siehe Robertson, Sanders, Seymour und Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

BEARBEITEN: Wie Mathieu betont, sind kubische Graphen mit Brücken niemals mit 3 Kanten färbbar.

Emil
quelle
5
Kubische Graphen mit einer Brücke können niemals mit drei Kanten eingefärbt werden. Dies folgt aus dem "Parity Lemma", siehe zum Beispiel die Bemerkung unter Lemma 2.1 in combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Colin McQuillan
1
Um genau zu sein, steht die Äquivalenz zwischen Kanten-Färbung und 4- Farben nur für brückenlose kubische ebene Graphen. 34
Mathieu Chapelle
@Emil, ich verstehe nicht, wie es bedeuten würde, dass kubische PLANARE Graphen mit Brücken niemals 3-kantig färbbar sind.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany Bei zwei Farben a und b in einer d-Kantenfärbung eines d-regulären Graphen (d> = 2) ist der durch die mit a oder b gefärbten Kanten induzierte Teilgraph eine disjunkte Vereinigung von geraden Zyklen. Daraus folgt das Paritäts-Lemma: Wenn X eine richtige nicht leere Teilmenge von V (G) ist und F der durch X induzierte Schnitt ist, dann ist für alle Farben a und b die Parität der Anzahl der Kanten von X mit der Farbe a gleich der Parität der Anzahl der Kanten von X farbig b. Ergo kann jeder d-reguläre Graph (d> = 2) mit einer Brücke nicht d-kantenfärbbar sein, unabhängig davon, ob er planar ist oder nicht.
Leandro Zatesko
5

Die dreieckige Einfärbung dreieckfreier Grafiken mit maximalem Grad 3 ist ebenfalls NP-vollständig, siehe 10.1016 / S0096-3003 (96) 00021-5.

Diamantis Korea
quelle