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”. $NP$

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

Ponadto, przypuszcza się, że -edge barwiący -hard dla płaskich wykresów z maksymalnym stopniu {4,5}. $\Delta$ $NP$ $\Delta \in$

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

— 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 ...

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

$3$

4

$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

4

Ten dokument może Cię zainteresować:

http://cs.nyu.edu/cole/papers/edge_col.pdf

— Joseph Malkevitch
źródło

Alternatywnie, dx.doi.org/10.1007/s00453-007-9044-3 Dziwne, że jest to jeden z pierwszych hitów, gdy korzystasz z Google <kolorowanie płaskich wykresów krawędzi>.

— RJK