Grid minor dalam digraf

8

Thor Johnson, et al, dalam makalah mereka: Sutradara Pohon Lebar , memperkenalkan definisi untuk diarahkan jaringan , dan mereka menduga:Jk

Untuk setiap bilangan bulat k terdapat bilangan bulat N sehingga setiap digraph dengan pohon-lebar N atau lebih memiliki minor isomorfik ke J k .(5.1)kNNJk

Dan mereka melanjutkan dengan mengatakan:

Kami telah meyakinkan diri sendiri bahwa berlaku untuk digraf planar, tetapi kasus umum terbuka.(5.1)

Dan aku mencari kertas ini tidak diterbitkan (bagaimana mereka membuktikan dugaan untuk grafik di-planar), atau hal-hal yang terkait dalam kasus ini, sebenarnya cara menggunakan grid seperti (saya berarti ).Jk

reference-request graph-theory co.combinatorics graph-minor Saeed
sumber
2
Apakah Anda sudah menghubungi penulis tentang hal itu? Saya ingin tahu tentang itu juga. Bagi saya, pernyataan "Kami telah meyakinkan diri kami sendiri" tidak selalu menyiratkan bahwa mereka memiliki versi sepenuhnya dari argumen mereka.
Hermann Gruber

Jawaban:

10

Ada pracetak baru oleh Stephan Kreutzer dan Ken-ichi Kawarabayashi, di mana mereka tampaknya menunjukkan bahwa pernyataan (5.1) itu benar untuk semua digraf.

Stephan Kreutzer dan Ken-ichi Kawarabayashi: Teorema grid yang diarahkan . arXiv: 1411.5681 [cs.DM]

EDIT (16 Juni 2015):

Versi singkat dari makalah mereka muncul di sini:

Ken-ichi Kawarabayashi, Stephan Kreutzer. Teorema Grid Sutradara. Dalam: Rocco A. Servedio, Ronitt Rubinfeld (eds.), Prosiding ACM Tahunan Empat Puluh Ketujuh tentang Simposium tentang Teori Komputasi 2015. hlm. 655-664

Hermann Gruber
sumber
8

JK

EDIT: Makalah tersebut sekarang tersedia untuk umum:

http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.6

Johnson et al. Makalah 2001, sekarang tersedia untuk umum:

Tidak Termasuk Kotak Kecil Di Digraf Planar

Saeed
sumber
1
Saya tertarik mendengar tentang hasil ini. Saya akan menghargai Anda memberikan referensi terbaru. Apakah Anda mendapatkan kertas konsep dari Seymour etal?
Chandra Chekuri
1
@ChandraChekuri, Sebenarnya orang lain mendapatkan kertas konsep (bertahun-tahun yang lalu), dan beberapa hari yang lalu saya hanya melihat kertas selama beberapa jam. di halaman pertama, salah satu penulis utama menulis "Jangan mendistribusikan". jadi kita tidak bisa berharap untuk memilikinya, tetapi hasil baru akan dipublikasikan di SODA2013, dan saya bisa merujuk ke hasil baru ini (saat dipublikasikan).
Saeed