Apakah klaim berikut diketahui?
Klaim : Untuk setiap grafik dengan simpul ada pewarnaan sehingga setiap set independen diwarnai oleh paling banyak warna .n G O ( √
sumber
Apakah klaim berikut diketahui?
Klaim : Untuk setiap grafik dengan simpul ada pewarnaan sehingga setiap set independen diwarnai oleh paling banyak warna .n G O ( √
Klaim berikut diketahui oleh saya, tetapi mungkin tidak dihitung karena tidak dipublikasikan: Setiap grafik pada simpul dapat diwarnai sehingga setiap subgraf diinduksi dari bilangan kromatik paling banyak digunakan paling banyak warna, di mana .H k χ ( H ) + B B ( B + 1 ) ≤ 2 k n
Ini adalah bukti dengan induksi; motivasi adalah untuk mempertimbangkan pewarnaan yang menggunakan beberapa warna tidak hanya pada grafik tetapi juga pada semua subgraph yang diinduksi. Saya tidak mengetahui hasil apa pun yang dipublikasikan.
Tidak persis seperti yang Anda minta, tapi ini batas bawah - grafik di mana pewarnaan apa pun akan menghasilkan set independen yang diwarnai oleh warna:
Ambil salinan , dan menghubungkan semua simpul ke simpul tunggal . K √ s
Jelas, setiap set simpul dari berbeda adalah independen, dan di setiap salinan Anda dapat menemukan setidaknya satu warna "baru". KK √
Ini lebih rendah terikat dapat dengan mudah ditingkatkan untuk atau jadi jika kita menghubungkan K 1 , K 2 , . . ke satu titik, tetapi hanya tersisa Ω ( √warna.
Bagaimana dengan bukti berikut? Jika , maka klaim itu berlaku jelas. Misalkan sebaliknya, dan biarkansayamenjadi set independenGdengan kardinalitas maksimumα. Warnasayadengan warna 1, dan warna rekursif grafikG-Idengan warna2,. . . ,c. Sekarang, jikaKadalah himpunan bebas dariG, pertimbangkanK'=K-Aku. Dengan hipotesis induksi,K'diwarnai dengan paling √α(G)≤n−−√ I G α I G−I 2,...,c K G K′=K−I K′ warna α , dan dengan demikianKdiwarnai dengan paling banyak1+ √n−α−−−−−√ K warna; ketidaksetaraan dipegang oleh asumsi bahwaα≥ √1+n−α−−−−−√≤n−−√ .α≥n−−√
sumber