Hubungan antara lebar pohon dan jumlah klik

Apakah ada kelas grafik yang bagus yang lebar pohon dibatasi oleh fungsi dari angka klik , yaitu ? $tw(G)$ $\omega(G)$ $tw(G)\leq f(\omega(G))$

Sebagai contoh, ini adalah fakta klasik bahwa untuk setiap grafik chordal , kita memiliki . Jadi, kelas yang berhubungan dengan grafik chordal bisa menjadi kandidat yang baik. $G$ $tw(G)=\omega(G)-1$

graph-theory treewidth Florent Foucaud
sumber

tw untuk grafik chordal.

(G) = ω (G) - 1

$(G) = \omega(G) - 1$

Yixin Cao

karena treewidth ditutup dengan mengambil subgraph, jika grafik memiliki sebagai subgraph maka treewidth G harus setidaknya treewidth dari , yaitu .

G

$G$

K_{n}

$K_n$

K_{n}

$K_n$

n - 1

$n-1$

Mateus de Oliveira Oliveira

@Matheus saya pikir pertanyaannya adalah sebaliknya. Dia meminta batas atas dan teladan Anda memberi batas bawah.

Vinicius dos Santos

@ Bart Jansen: grafik split bersifat chordal.

Florent Foucaud

@FlorentFoucaud, Anda harus mempertimbangkan untuk mengubah hasil edit Anda menjadi jawaban.

Vinicius dos Santos

Jawaban:

Pada halaman ini teorema disebutkan yang menyediakan kelas-kelas seperti:

Teorema (Scheffler [1]) Jika adalah grafik perpotongan dari subgraph yang terhubung dari grafik , maka . $G$ $H$ $tw(G)\leq tw(H)\omega(G)-1$

Ini menggeneralisasi batas untuk grafik chordal (yang adalah pohon) dan juga berlaku untuk grafik busur-lingkaran (maka adalah siklus). Saya tidak tahu apakah kelas "standar" lain ditangkap oleh teorema ini. $H$ $H$

[1] P. Scheffler, Grafik apa yang membatasi lebar pohon? Rostocker Math. Kolloq. 41 (1990) 31-38.

Florent Foucaud
sumber

"tidak dapat diakses"? Anda maksud kertas tidak online?

vzn

Sebenarnya pada awalnya saya pikir ini adalah pembicaraan konferensi tetapi jelas ini memiliki beberapa nomor halaman. Ada situs web untuk jurnal ( math.uni-rostock.de/math/pub/romako ), saya sudah bertanya apakah mungkin untuk mendapatkan salinannya.

Florent Foucaud

Saya pikir itu juga tidak sulit untuk membuktikannya sendiri. Mungkin lebih cepat daripada menerima salinan kertas :)

Saeed

@ Saeed Mungkin, tapi saya terutama berharap untuk menemukan beberapa diskusi tentang topik di makalah itu!

Florent Foucaud

$G$ $tw(G)\leq 3\omega(G)/2-2$

$G$ $tw(G)\leq 6\omega(G)-1$ $G$

[1] K. Cameron, S. Chaplick, CT Hoang. Pada struktur (pan, bahkan lubang) grafik -gratis, 2015. https://arxiv.org/abs/1508.03062

[2] K. Cameron, MVG da Silva, S. Huang, K. Vušković. Struktur dan algoritma untuk (tutup, bahkan lubang) grafik -gratis, 2016. https://arxiv.org/abs/1611.08066

Florent Foucaud
sumber