Alasan grafik mana yang mungkin tidak dapat diwarnai

Sementara sedikit beralasan pada pertanyaan ini , saya telah mencoba untuk mengidentifikasi semua alasan berbeda yang membuat grafik mungkin gagal k menjadi berwarna. Ini adalah satu-satunya 2 alasan yang dapat saya identifikasi sejauh ini:$G = (V_G,E_G)$$k$

1. mengandung sebuah klik dari ukuran k + 1 . Ini adalah alasan yang jelas.$G$$k+1$

2. Terdapat subgraf dari G sehingga kedua pernyataan berikut ini benar:$H = (V_H, E_H)$$G$

   • tidak k - 1 dapat berwarna.$H$$k-1$
   • . Dengan kata lain terdapat node x di G tetapi tidak di H , sehingga x terhubung ke setiap node di H .$\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$$x$$G$$H$$x$$H$

Kita dapat melihat 2 alasan di atas sebagai aturan. Dengan rekursif menerapkan mereka, hanya 2 cara untuk membangun non grafik yg berhasil yang tidak mengandung k + 1 clique adalah:$k$$k+1$

1. Mulai dari siklus dengan panjang genap (yang warna), lalu terapkan aturan 2 untuk k - 1 kali. Perhatikan bahwa tepi tidak dianggap sebagai siklus dengan panjang 2 (jika tidak, proses ini akan memiliki efek membangun klik k + 1 ).$2$$k-1$$2$$k+1$
2. Mulai dari siklus dengan panjang ganjil (yaitu warna), lalu terapkan aturan 2 untuk k - 2 kali. Panjang siklus awal harus lebih besar dari 3 (jika tidak, proses ini akan memiliki efek membangun klik k + 1 ).$3$$k-2$$3$$k+1$

Pertanyaan

Apakah ada alasan lagi, selain yang 2 di atas, yang membuat grafik non yg berhasil?$k$

$\ $
Pembaruan 30/11/2012

Lebih tepatnya, yang saya butuhkan adalah beberapa teorema bentuk:

Grafik memiliki angka kromatik χ ( G ) = k + 1 jika dan hanya jika ...$G$$\chi(G) = k + 1$

Hajos kalkulus , ditunjukkan oleh Yuval Filmus dalam jawabannya, adalah contoh sempurna dari apa yang saya cari, sebagai grafik memiliki bilangan kromatik χ ( G ) = k + 1 jika dan hanya jika dapat diturunkan dari aksioma K k + 1 dengan berulang kali menerapkan 2 aturan inferensi dari kalkulus. Angka Hajo h ( G ) kemudian merupakan jumlah minimum langkah yang diperlukan untuk memperoleh G (yaitu, itu adalah panjang dari bukti terpendek).$G$$\chi(G) = k + 1$$K_{k+1}$$h(G)$$G$

Sangat menarik bahwa:

• Pertanyaan apakah ada grafik yang h ( G ) eksponensial dalam ukuran G masih terbuka.$G$$h(G)$$G$
• Jika seperti tidak ada, maka N P = c o N P .$G$$NP = coNP$

Anda harus memeriksa kalkulus Hajós . Hajós menunjukkan bahwa setiap grafik dengan angka berwarna setidaknya memiliki subgrafi yang memiliki "alasan" untuk membutuhkan warna k . Alasan yang dimaksud adalah sistem bukti untuk membutuhkan warna k . Satu-satunya aksioma adalah K k , dan ada dua aturan inferensi. Lihat juga makalah ini oleh Pitassi dan Urquhart tentang efisiensi sistem bukti ini.$k$$k$$k$$K_k$

Jawaban parsial, karena saya tidak tahu "alasan" yang bagus yang dapat digeneralisasi, tetapi grafik berikut (tanpa malu-malu didatangkan dari sini ):

Tidak 3-warna, tetapi jelas 4-warna (menjadi planar), dan tidak mengandung , atau siklus apa pun dengan simpul tambahan yang terhubung ke semua simpul siklus (kecuali jika saya kehilangan sesuatu, tetapi satu-satunya simpul terhubung ke simpul dan tetangganya berada dalam 3-siklus). Mengambil lebih jauh, Anda bisa menerapkan versi aturan 2 untuk mendapatkan grafik nomor berwarna 5.$K_{4}$

Saya menduga bahwa untuk setiap genus yang diberikan, ada grafik dari nomor kromatik minimum tertentu (lihat dugaan Heawood ) yang tidak mengikuti aturan 1 atau 2. Tentu saja saya tidak punya bukti selain intuisi.

Lovasz menemukan penghalang topologis untuk k-colorability dan menggunakan teorinya untuk menyelesaikan dugaan Knaser. Teorema-Nya adalah sebagai berikut. Biarkan G menjadi grafik yang terhubung, dan biarkan N (G) menjadi kompleks sederhana yang wajahnya adalah himpunan bagian dari V yang memiliki tetangga yang sama. Kemudian jika N (K) terhubung dengan k (yaitu, semua kelompok homologi tereduksinya adalah 0 hingga dimensi k-1) maka jumlah warna yang diperlukan untuk warna G setidaknya k + 3.

Tidak memiliki set independen yang besar bisa sama pentingnya dengan memiliki klik besar.

Suatu halangan penting untuk grafik agar tidak k-colorable adalah bahwa ukuran maksimum dari set independen lebih kecil dari n / k, di mana n adalah jumlah simpul. Ini adalah penghalang yang sangat penting. Sebagai contoh, ini menyiratkan bahwa grafik acak dalam G (n, 1/2) memiliki bilangan kromatik setidaknya n / log n.

Obstruksi yang lebih halus adalah bahwa untuk setiap tugas bobot nonnegatif untuk simpul tidak ada set independen yang menangkap sebagian 1/5 (atau lebih) dari total berat. Perhatikan bahwa ini juga termasuk "tidak ada penghalang klik". LP-dualitas memberitahu Anda bahwa obstruksi ini setara dengan "bilangan kromatik fraksional" dari G yang lebih besar dari k.

Ada juga penghalang untuk k-colorability dari sifat yang berbeda yang kadang-kadang melampaui penghalang bilangan kromatik fraksional. Saya akan mencurahkan usaha terpisah untuk mereka.

$G$$\chi(G)=k+1$ jika dan hanya jika ...":

$G$$\chi(G)\ge k$$G$$k-1$