Kompleksitas pewarnaan tepi dalam grafik planar

15

Pewarnaan 3-sisi dari grafik kubik adalah -complete. Teorema Empat Warna setara dengan "Setiap grafik bridgeless planar kubik adalah 3-sisi yang dapat diwarnai".NP

Apa kompleksitas pewarnaan 3-sisi grafik planar kubik?

Juga, Hal ini menduga bahwa -edge pewarnaan adalah N P -Hard untuk grafik planar dengan tingkat maksimum Δ ∈ {4,5}.ΔNPΔ∈

Apakah ada kemajuan yang dicapai untuk menyelesaikan dugaan ini?

Marek Chrobak dan Takao Nishizeki. Algoritma pewarnaan tepi yang ditingkatkan untuk grafik planar. Jurnal Algoritma, 11: 102-116, 1990

cc.complexity-theory graph-theory np-hardness graph-colouring Mohammad Al-Turkistany
sumber
Bukankah baris 2 pada tabel 1 di dx.doi.org/10.1007/s00453-007-9044-3 berarti bahwa "pewarnaan 3-sisi grafik planar kubik" secara polinomi dapat dipecahkan?
Oleksandr Bondarenko
Entri tabel mengacu pada kertas Robertson, Sanders, Seymour, dan Thomas Four Coloring yang berkaitan dengan grafik planar kubus Bridgeless .
Mohammad Al-Turkistany
+1 pertanyaan yang bagus, saya punya yang serupa, tetapi yang lebih praktis ...
draks ...
Hai, apakah Anda tahu jika ada kemajuan untuk pewarnaan 3-tepi pada grafik kubik pada torus ganda ?
Drak ...

Jawaban:

15

Setiap grafik planar kubik tanpa bridg dapat berwarna 3-edge dalam waktu kuadrat, karena tugas ini setara dengan empat warna grafik planar, yang dapat dilakukan dalam waktu kuadratik. (Lihat Robertson, Sanders, Seymour dan Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDIT: Seperti yang ditunjukkan Mathieu, grafik kubik dengan jembatan tidak pernah berwarna 3-tepi.

Emil
sumber
5
Grafik kubik dengan jembatan tidak pernah bisa 3-edge-colourable. Ini mengikuti dari "Parity Lemma" misalnya, lihat komentar di bawah Lemma 2.1 di combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Colin McQuillan
1
Tepatnya, kesetaraan antara warna tepi dan 4- warna hanya untuk grafik planar kubik tanpa jembatan . 34
Mathieu Chapelle
@ Emil, saya tidak melihat bagaimana hal itu menyiratkan bahwa grafik PLANAR kubik dengan jembatan tidak pernah bisa 3-edge colourable.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany Diberi dua warna a dan b dalam pewarnaan d-edge dari grafik d-regular (d> = 2), subgraph yang diinduksi oleh tepi berwarna a atau b adalah perpaduan yang tidak terpisahkan dari siklus genap. Dari sini, ikuti Parity Lemma: Jika X adalah subset non-kosong V (G) yang tepat dan F adalah potongan yang disebabkan oleh X, maka untuk semua warna a dan b, paritas jumlah tepi X berwarna a adalah sama dengan paritas jumlah tepi berwarna X b. Ergo, grafik d-reguler (d> = 2) dengan bridge tidak dapat d-edge-colourable, terlepas dari planar atau tidak.
Leandro Zatesko
5

Pewarnaan 3-sisi dari grafik bebas-segitiga dengan derajat maksimum 3 juga NP-complete, lihat 10.1016 / S0096-3003 (96) 00021-5.

Diamantis Koreas
sumber