Apakah lebar klik dipertahankan di bawah kontraksi tepi?

13

Misalkan adalah kelas grafik dengan lebar klik terikat. Dalam setiap grafik di G beberapa sisi dikontrak (misalnya secara acak). Apakah sekarang klik-lebar masih terikat?GG

Dalam hal ini (secara umum) tidak lagi dibatasi, saya akan sangat tertarik pada contoh tandingan.

Martin Lackner
sumber

Jawaban:

16

G{x,y}E(G)cw(G)<cw(Gx,y)Gx,yG{x,y}

Mathieu Chapelle
sumber
Terima kasih banyak atas jawaban Anda! Itu referensi berharga bagi saya. Jika tidak ada yang memecahkannya sementara waktu, pertanyaan saya kurang lebih dijawab :)
Martin Lackner
Bukankah itu masalah arah yang berlawanan dari apa yang ditanyakan di sini?
Tsuyoshi Ito
Hanya dalam arti bahwa pertanyaan ini meminta sampel balik.
Martin Lackner
17

Makalah baru-baru ini akhirnya membuktikan bahwa kontraksi tepi tidak mempertahankan properti yang satu set grafik telah terikat lebar-klik.

pengguna13136
sumber