Złożoność kolorowania krawędzi na wykresach płaskich

15

3 krawędzi barwienia wykresów sześcienny -Complete. Twierdzenie o czterech kolorach jest równoważne z tym, że „Każdy sześcienny płaski wykres bez mostka ma 3 krawędzie do pokolorowania”.N.P.

Jaka jest złożoność 3-krawędziowego kolorowania sześciennych wykresów płaskich?

Ponadto, przypuszcza się, że -edge barwiący N P -hard dla płaskich wykresów z maksymalnym stopniu hemibursztynianu ∈ {4,5}.ΔN.P.Δ∈

Czy poczyniono jakieś postępy w rozwiązaniu tego przypuszczenia?

Marek Chrobak i Takao Nishizeki. Ulepszone algorytmy kolorowania krawędzi dla wykresów płaskich. Journal of Al Algorytmy, 11: 102-116, 1990

cc.complexity-theory graph-theory np-hardness graph-colouring Mohammad Al-Turkistany
źródło
Czy wiersz 2 w tabeli 1 w dx.doi.org/10.1007/s00453-007-9044-3 nie oznacza, że ​​„3-krawędziowe barwienie sześciennych wykresów płaskich” jest wielomianowo możliwe do rozwiązania?
Oleksandr Bondarenko
Wpis w tabeli odnosi się do papieru Robertsona, Sandersa, Seymour i Thomasa Four Coloring, który dotyczy sześciennych wykresów płaskich Bridgeless .
Mohammad Al-Turkistany
+1 świetne pytanie, mam podobne, ale bardziej praktyczne ...
draks ...
Cześć, czy wiesz, czy jest jakiś postęp w 3-krawędziowym kolorowaniu grafów sześciennych na podwójnym torusie ?
draks ...

Odpowiedzi:

15

Każdy płaski wykres sześcienny pozbawiony mostów może mieć kwadratowy kolor w czasie kwadratowym, ponieważ to zadanie jest równoważne czterokolorowemu wykresowi płaskiemu, który można wykonać w czasie kwadratowym. (Zobacz Robertson, Sanders, Seymour i Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDYCJA: Jak zauważa Mathieu, sześcienne wykresy z mostami nigdy nie są trójwymiarowe.

Emil
źródło
5
Sześcienne wykresy z mostem nigdy nie są trójwymiarowe. Wynika to z „parytetu Lemma”, na przykład patrz uwaga pod Lemma 2.1 w combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Colin McQuillan
1
3)4
@Emil, nie rozumiem, jak by to sugerowało, że sześcienne wykresy PLANAR z mostami nigdy nie są trójwymiarowe.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany Biorąc pod uwagę dwa kolory aib w kolorystyce krawędzi d wykresu regularnego d (d> = 2), wykres podrzędny wywołany przez krawędzie w kolorze a lub b stanowi rozłączny związek parzystych cykli. Wynika z tego lemat parzystości: jeśli X jest właściwym niepustym podzbiorem V (G), a F jest cięciem indukowanym przez X, to dla wszystkich kolorów a i b parzystość liczby krawędzi X w kolorze a wynosi równa parzystości liczby krawędzi koloru X w kolorze b. Ergo, dowolny wykres regularny d (d> = 2) z mostem nie może być d-kolorowy-bez względu na to, czy jest płaski, czy nie.
Leandro Zatesko
5

Trójkątne zabarwienie grafów bez trójkątów o maksymalnym stopniu 3 jest również NP-zupełne, patrz 10.1016 / S0096-3003 (96) 00021-5.

Diamantis Koreas
źródło