Pewarnaan grafik meminimalkan jumlah warna di setiap set independen

11

Apakah klaim berikut diketahui?

Klaim : Untuk setiap grafik dengan simpul ada pewarnaan sehingga setiap set independen diwarnai oleh paling banyak warna .n G O ( GnGO(n)

Igor Shinkar
sumber

Jawaban:

11

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 nnHkχ(H)+BB(B+1)2kn

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.

Aravind
sumber
10

Tidak persis seperti yang Anda minta, tapi ini batas bawah - grafik di mana pewarnaan apa pun akan menghasilkan set independen yang diwarnai oleh warna:n

Ambil salinan , dan menghubungkan semua simpul ke simpul tunggal . Kn sKns

Jelas, setiap set simpul dari berbeda adalah independen, dan di setiap salinan Anda dapat menemukan setidaknya satu warna "baru". KKnKKn

Ini lebih rendah terikat dapat dengan mudah ditingkatkan untuk atau jadi jika kita menghubungkan K 1 , K 2 , . . ke satu titik, tetapi hanya tersisa Ω ( 2nK1,K2,..warna.Ω(n)

BPR
sumber
Contoh kedua tampaknya tidak meningkatkan ikatan. Saya pikir IS apa pun dapat diwarnai menggunakan . Misalnya, untuk n = 9,K1diwarnai oleh biru,K2oleh hijau dan merah, danK3oleh biru, hijau dan merah. IS maksimal apa pun diwarnai oleh 2 warna, bukan 3.22n/3K1K2K3
user15669
Saya tidak yakin apa yang Anda maksud. Contoh kedua memang meningkatkan batas, tetapi tidak asimtotik. Anda dapat membuat ~ berukuran IS berwarna-warni menggunakan titik dariK1, titik dariK2dengan warna yang berbeda, dan seterusnya (dariKikita akan mengambil titik yang diwarnai oleh warna yang belum ada di IS kita). Dan ini berlaku untuk setiap mewarnaiG. 2nK1K2KiG
RB
Juga, dalam contoh Anda, IS yang mencakup titik biru dari , hijau dari K 2 dan merah dari K 3 diwarnai oleh 3 warna. K1K2K3
RB
1
@RB, terima kasih atas contohnya. grafik kedua Anda memberikan batas bawah kira-kira , ini adalah angka sehingga1+2++t=n. t2n1+2++t=n
Igor Shinkar
5

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)nIGαIGI2,...,cKGK=KIK warna α , dan dengan demikianKdiwarnai dengan paling banyak1+nαK warna; ketidaksetaraan dipegang oleh asumsi bahwaα1+nαn .αn

Super8
sumber
1
, tetapi bukti ini mungkin dapat dimodifikasi untuk menunjukkan bahwa untukϵ>0IS apa pun yang diwarnai paling banyak(1+ϵ)1+nn>nϵ>0warna. Bagaimanapun, ini adalah permintaan referensi, bukan permintaan untuk bukti. (1+ϵ)n+Cϵ
user15669
1
Memang, buktinya harus bekerja dengan mengganti dengan2n . Saya minta maaf karena telah melewatkan bagian "permintaan referensi", tetapi bukankah hasil ini dianggap sebagai cerita rakyat? BTW, saya orang yang sama seperti di atas tetapi saya perlu menemukan cara untuk mengkonsolidasikan profil saya yang berbeda, saya mungkin harus meminta ini di meta.cstheory.stackexchange. 2n
Super0
(pada permintaan penggabungan profil) meta adalah tempat yang baik untuk mengirim permintaan semacam itu.
Suresh Venkat