Buat daftar pewarnaan grafik yang sesuai dengan sistem tripel Steiner

Aug 20 2020

Pertimbangkan sistem triple Steiner $S(2,3,n)$ untuk bilangan bulat yang cocok $n$. Kami mendefinisikan grafik$G$ dengan semua simpul sama persis dengan blok dari sistem rangkap tiga steiner di atas dan dua titik yang berdekatan jika perpotongan blok yang sesuai dengannya di STS tidak kosong.

Apakah ada hasil pada pemilihan grafik semacam itu? Atau, setidaknya, apakah ada yang diketahui tentang bilangan kromatik grafik semacam itu? Saya pikir angka-angka ini terkait erat dengan bilangan kromatik dan kemampuan memilih grafik Kneser umum$K(n,3,2)$. Tingkat maksimum dari grafik ini tampaknya$\frac{3(n-2)}{2}$ dan ukuran klik adalah $\frac{n-2}{2}$. Ada petunjuk? Terimakasih sebelumnya.

Jawaban

1 vidyarthi Aug 22 2020 at 23:16

Grafik tersebut dapat dilihat sebagai grafik garis hipergraf linier peringkat tiga. Beberapa hasil pewarnaan daftar ini diketahui di sini . Daftar nomor kromatik ini dibatasi oleh$n$.