Kompleksitas pewarnaan grafik

Misalkan adalah grafik dengan angka pewarnaan . Pertimbangkan permainan berikut antara Alice dan Bob. Pada setiap putaran, Alice memilih sebuah titik, dan Bob menjawab dengan warna di untuk titik ini. Permainan berakhir ketika tepi monokromatik ditemukan. Biarkan menjadi panjang maksimal permainan di bawah permainan optimal oleh kedua pemain (Alice ingin memperpendek permainan, Bob ingin menunda mungkin). Misalnya, dan . $G$ $d = \chi(G)$ $\{1,\ldots,d-1\}$ $X(G)$ $X(K_n) = n$ $X(C_{2n+1}) = \Theta(\log n)$

Apakah game ini dikenal?

reference-request graph-theory co.combinatorics graph-colouring decision-trees Yuval Filmus
sumber

Saya pikir Anda mungkin dapat memodelkan ini sebagai game Ehrenfeucht – Fraïssé .

Tyson Williams

tampaknya akan sangat terkait dengan algoritma pewarnaan grafik serakah, kan? di mana ada banyak .... mirip dengan masalah SAT di mana salah satu variabel "dipaksa" setelah beberapa traversal DPLL ... yang saya percaya juga disebut "tulang punggung" di SAT

vzn

Mengapa Anda menggunakan d − 1? Saya pikir lebih wajar untuk membuat parameter permainan dengan grafik G dan jumlah k dari warna yang diizinkan dan mempertimbangkan kuantitas analog X (G, k). Tentu saja, jika k≥χ (G), maka Bob menang, dan karenanya dalam hal ini, X (G, k) harus didefinisikan sebagai ∞ atau n +1.

Tsuyoshi Ito

@Tsuyoshi: adalah pilihan sewenang-wenang yang dirancang untuk memaksimalkan . Dalam aplikasi yang saya pikirkan, tidak masuk akal.

k = d - 1

$k = d-1$

X (G)

$X(G)$

k \geq χ (G)

$k \geq \chi(G)$

Yuval Filmus

@Tyson: Faktanya, adalah kompleksitas pohon keputusan dari permainan di mana, mengingat pewarnaan , kami ingin menemukan tepi yang dilanggar.

X (G)

$X(G)$

d - 1

$d-1$

G

$G$

Yuval Filmus

Kompleksitas pewarnaan grafik

Jawaban: