Bisakah angka berwarna mudah dihitung ketika pewarnaan sulit untuk beberapa kelas grafik?

Pertanyaan serupa ditanyakan sebelumnya, tetapi ada kesalahan di dalamnya sehingga dibiarkan tidak dijawab kelas Grafik dengan nomor berwarna mudah, tetapi pewarnaan NP-keras

Apakah ada rangkaian grafik tak terbatas seperti: $C$

Ada algoritma polinomial yang mengenali untuk setiap grafik apakah milik $G$ $G$ $C$
Ada algoritma waktu polinomial yang menghitung bilangan kromatik untuk setiap $\chi(g)$ $g \in C$
Manusia tidak tahu algoritma waktu polinomial untuk menghitung pewarnaan yang tepat untuk , atau (yang lebih baik) ada bukti bahwa algoritma semacam itu (dengan asumsi yang masuk akal) tidak ada. $C$

graph-theory graph-algorithms Janczar Knurek
sumber

Ini juga pertanyaan yang agak terkait; beberapa jawaban mungkin memberikan beberapa ide: cstheory.stackexchange.com/questions/1848/…

Jukka Suomela

Ya, bagian tentang grafik gratis P_5 menarik dan bermanfaat bagi saya, tapi bukan itu yang saya bicarakan.

Janczar Knurek

χ (g)

$\chi(g)$

Jawaban:

Iya. Karena 3-COLORING adalah FNP-complete, untuk setiap masalah di FNP kita dapat membuat grafik G yang 3-colorable jika dan hanya jika masalahnya memiliki solusi. Jadi, Anda dapat memilih masalah favorit Anda dari TFNP \ FP (jika tidak kosong!), Seperti menemukan faktor bilangan komposit, atau siklus Hamiltonian kedua dalam grafik 3-reguler, dan mengubahnya menjadi grafik.

$N$ $G(N)$ $G(N)$ $N$ $N$ $G(N)$ $3$ $G(N)$ $d$ $N$ $d$ $x_1\ldots x_{n}$ $N$ $n$ $3$ $x_i$ $d$ $3$

domotorp
sumber

Sejujurnya, saya tidak mengerti maksud Anda sama sekali ... Bisakah Anda mengatakannya lagi, tetapi dengan sedikit formalisme? Maksud saya, misalnya saya tidak melihat bagaimana kondisi 1. memegang jawaban Anda ...

Janczar Knurek

Saya telah memperbarui jawaban saya.

domotorp

Properti yang Anda gunakan adalah, pada dasarnya, FNP-kelengkapan varian masalah pencarian dari 3-COLORING. Ini tidak mengikuti hanya dari NP-kelengkapan 3-COLORING, maka kalimat pertama menyesatkan.

Emil Jeřábek

Oke, tapi tetap saja, masih ada masalah untuk memutuskan apakah grafik dari formulir ini. Saya mengerti bahwa ada beberapa alat standar, tetapi saya menganggap Anda tidak memeriksa, tetapi Anda hanya berpikir mereka bisa bekerja? Bagaimanapun, terima kasih, atas jawaban.

Janczar Knurek

@Emil Ups, saya pikir itu memang mengikuti! Terima kasih atas koreksinya.

domotorp