Zależność między szerokością drzewa a liczbą kliki

Czy istnieją jakieś ładne klasy grafów, dla których szerokość drzewa jest ograniczona górną funkcją liczby kliki , tj. ? $tw(G)$ $\omega(G)$ $tw(G)\leq f(\omega(G))$

Na przykład, klasycznym faktem jest, że dla każdego wykresu akordowego mamy . Tak więc klasy związane z grafami akordowymi mogą być dobrymi kandydatami. $G$ $tw(G)=\omega(G)-1$

graph-theory treewidth Florent Foucaud
źródło

tw dla wykresów akordowych.

(G) = ω (G) - 1

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

Yixin Cao

ponieważ szerokość grzbietu jest zamknięta przy pobieraniu podgrafów, jeśli wykres ma jako podgraf, wówczas szerokość G musi wynosić co najmniej szerokość , czyli .

G

$G$

K_{n}

$K_n$

K_{n}

$K_n$

n - 1

$n-1$

Mateus de Oliveira Oliveira

@ Matheus Myślę, że pytanie jest odwrotnie. Prosi o górną granicę, a twój przykład podaje dolną granicę.

Vinicius dos Santos

@Bart Jansen: podzielone wykresy są akordowe.

Florent Foucaud

@FlorentFoucaud, powinieneś rozważyć przekształcenie swojej edycji w odpowiedź.

Vinicius dos Santos

Odpowiedzi:

Na tej stronie wspomniane jest twierdzenie, które zapewnia takie klasy:

Twierdzenie (Scheffler [1]) Jeśli jest wykresem przecięcia połączonych podgraphów innego wykresu , to . $G$ $H$ $tw(G)\leq tw(H)\omega(G)-1$

Uogólnia to ograniczenie dla wykresów akordowych (dla których jest drzewem), a także stosuje się do wykresów z łukiem kołowym (wtedy jest cyklem). Nie wiem, czy to „twierdzenie” obejmuje inne „standardowe” klasy. $H$ $H$

[1] P. Scheffler, Jakie wykresy ograniczają szerokość drzewa? Rostocker Math. Kolloq. 41 (1990) 31–38.

Florent Foucaud
źródło

„niedostępny”? masz na myśli, że papier nie jest online?

vzn

Właściwie na początku myślałem, że to rozmowa konferencyjna, ale oczywiście ma kilka numerów stron. Jest strona internetowa czasopisma ( math.uni-rostock.de/math/pub/romako ), zapytałem, czy można uzyskać kopię.

Florent Foucaud

Myślę, że nie jest to trudne do udowodnienia samemu. Być może jest to szybsze niż otrzymanie kopii papieru :)

Saeed

@Saeed Możliwe, ale szczególnie mam nadzieję znaleźć dyskusję na ten temat w tym artykule!

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. O strukturze wykresów wolnych od (przesuwanie, nawet dziury), 2015. https://arxiv.org/abs/1508.03062

[2] K. Cameron, MVG da Silva, S. Huang, K. Vušković. Struktura i algorytmy dla wykresów wolnych od (cap, nawet hole), 2016. https://arxiv.org/abs/1611.08066

Florent Foucaud
źródło