Grafik kecil dengan celah antara bilangan kromatik dan vektor?

Saya mencari grafik kecil yang bilangan vektor kromatiknya lebih kecil dari angka kromatik, χ v ( G ) < χ ( G ) .$G$$\chi_v(G)<\chi(G)$

( memiliki vektor berwarna jumlah q jika ada tugas x : V → R d , di mana intuitif vektor terkait dengan simpul tetangga terpisah jauh Persyaratannya adalah. ⟨ X ( v ) , x ( w ) ⟩ ≤ - 1 / ( q - 1 ) . Misalnya, untuk q = 3 , simpul segitiga sudah mencukupi.)$G$$q$$x\colon V \rightarrow \mathbf R^d$$\langle x(v), x(w)\rangle \leq -1/(q-1)$$q=3$

Nomor vektor kromatik grafik tidak lebih besar dari angka kromatik: . Contoh diketahui dari grafik dengan χ v ( G ) = 3 χ ( G ) = n δ . (Makalah asli oleh Karger, Motwani, Sudan [JACM, 45: 246-265] ( manuskrip ) menunjukkan grafik Kneser umum, makalah yang lebih baru menggunakan konstruksi berdasarkan vektor satuan acak).$\chi_v(G)\leq \chi(G)$$\chi_v(G)=3$ $\chi(G)=n^\delta$

Saya pikir saya punya contoh grafik dengan χ v ( K ) = 4 dan χ ( K ) = 8 (berdasarkan perhitungan komputer). Grafik ini memiliki 20 simpul dan 90 tepi.$K$$\chi_v(K)=4$$\chi(K)=8$

Apakah ada contoh yang lebih kecil? Jalan yang menggiurkan adalah untuk menyediakan vektor konkret 3-warna dari grafik Chvatal atau Grötzsch, jika binatang seperti itu ada.

( tidak perlu menjadi integer, tapi akan menyenangkan Update:. Seperti yang ditunjukkan di bawah ini, kasus nonintegral memang mudah Terima kasih..)$\chi_v$

Pembaruan: Grötzsch dan Chvátal

Saya tidak bisa menahan diri untuk tidak memikirkan vektor 3-mewarnai grafik Chvátal dan Grötzsch.

Grafik Grötsch dapat berupa vektor 3-warna sebagai berikut: Letakkan derajat lima simpul di kutub Utara. Node 5 derajat-4 ditempatkan secara merata pada garis lintang yang sama, sekitar 77 derajat dari Utara: bayangkan sebuah pentragram yang dilukis di belahan bumi utara Bumi. 5 node yang tersisa (derajat 3) berakhir di belahan bumi Selatan, sekitar 135 derajat dari Utara. Memiliki garis bujur yang sama dengan 5 lainnya. (Saya akan mengunggah gambar saat saya punya, tetapi lebih sulit untuk menggambar garis geodesik di TikZ daripada yang saya kira.)

Menurut pemecah SDP, Chvátal juga mengakui vektor 3-pewarnaan, tetapi hasilnya hanya sekelompok vektor dalam 5 dimensi yang saya kesulitan menafsirkannya.

(Upaya ketiga gagal: Terinspirasi oleh konstruksi Yury, ambil 5-siklus dan tambahkan titik puncak yang berdekatan dengan yang lain. Grafik ini memiliki nomor berwarna 4. Tetapi menurut pemecah saya itu bukan vektor 3-colourable.)

$\chi_v(G)$$G=C_5$

$$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5) . \qquad\text{[Lovász]}$$

$\chi_v(G)$$G_1$$C_5^{(1)}$$C_5^{(2)}$$C_5^{(1)}$$C_5^{(2)}$$G_2=K_5$$G$$G_1$$G_2$

$$\begin{align*} \chi(G) &= \max(\chi(G_1), \chi(G_2)) = \chi(G_1) = 6.\\ \chi_v(G) &= \max(\chi_v(G_1), \chi_v(G_2)) = \max(2\cdot \sqrt{5}, 5) = 5. \end{align*}$$

Di sini disematkan grafik Grötzsch pada unit sphere: Ini sesuai dengan pewarnaan vektor dengan cara yang jelas; misalnya, simpul di kutub utara diwarnai dengan vektor (0,0,1).

Grafik Grötsch memiliki 3 jenis node. Gelar 5 node tunggal (di Utara). Lima derajat 4 node (di belahan bumi utara, sama dengan N, Anda bisa melihat 3 dari mereka). Lima derajat 3 node (di belahan bumi Selatan, sama dengan N, Anda dapat melihat 3 dari mereka).

N terhubung ke 5 tetangganya di belahan bumi Selatan dengan tepi hijau. (Perhatikan bahwa tepi hijau terlihat seperti insiden pada derajat 4-simpul di belahan bumi Utara, tetapi itu adalah artefak dari penanaman.)

Dilihat dari atas, Anda dapat melihat pentagram yang dijelaskan oleh node derajat 4, mirip dengan pada di pesawat:$C_5$

Akhirnya, pemandangan dari atas kutub Selatan:

Jika perhitungan saya dapat dipercaya, semua simpul yang berdekatan berada lebih dari 120 derajat dari satu sama lain, jadi ini merupakan vektor 3-warna yang valid. Grafik Grötzsch adalah 4-chromatic. 11 simpul, 20 tepi. Saya sangat senang dengan contoh ini karena pewarnaan vektor dalam 3 dimensi, untuk Anda dapat memvisualisasikannya. (Dan gambar hyperplanes acak untuk menjelaskan algoritma pewarnaan grafik KMS.)