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