Zabronione osoby niepełnoletnie w przypadku związanych z nimi wykresów rodzajów

Powszechnie wiadomo, że i są niedozwolone w przypadku wykresów planarnych. Istnieją setki zakazanych nieletnich dla wykresów osadzanych na torusie. Liczba niedozwolonych nieletnich dla wykresów osadzanych na powierzchni rodzaju g jest funkcją wykładniczą g . Moje pytanie brzmi: $K_5$ $K_{3,3}$

Ma wyraźnego wykresem o t wierzchołków (co nie jest kompletny panel) w taki sposób, jest zabronione moll na wykresie dla osadzanego na powierzchni rodzaju g , gdzie T jest funkcją g ? $G_t$ $G_t$

EDYCJA: Zrozumiałem, że znane jest następujące twierdzenie:

Dla każdej powierzchni Σ istnieje liczba całkowita r taka, że nie osadza się w Σ. $K_{3,r}$

Tak więc szukam który nie jest kompletnym wykresem, a nie kompletnym wykresem dwustronnym. $G_t$

graph-theory co.combinatorics graph-minor algebraic-topology Shiva Kintali
źródło

Czy chcesz mieć ładnie skonstruowaną, sparametryzowaną, nieskończoną rodzinę grafów (innych niż pełne), które są zabronione dla nieletnich na powierzchniach każdego rodzaju?

Derrick Stolee 9.11.11

@Bom. Tak. Dokładnie.

Shiva Kintali,

Następnie przeredagowałbym pytanie, używając tych terminów: „Czy istnieje (prosta do skonstruowania) rodzina grafów

tak że

jest minimalnym niedozwolonym znaczeniem dla grafów osadzanych na powierzchni rodzaju

{H_{g} : g \geq 1}

$\{ H_g : g \geq 1\}$

H_{g} ≇ K_{n}

$H_g \not\cong K_n$

g

$g$

Derrick Stolee 9.11.11

Ograniczenia „

nie są nieletni z

” nie mogą być tym, czego chcesz. Jeśli nie są nieletni z

, to

jest planarny i nie może być zabronionym nieletnim dla żadnego wyższego rodzaju.

K_{5}

$K_5$

K_{3, 3}

$K_{3,3}$

G

$G$

G

$G$

G

$G$

David Eppstein,

@DavidEppstein Usunąłem moje modyfikacje. Zasadniczo szukam przeszkód, które są „różne” od

K_{5}

$K_5$

K_{33}

$K_{33}$

Shiva Kintali

Odpowiedzi:

Rozłączny związek kopii (lub ) jest minimalną zabronioną drugorzędną dla wykresów z rodzaju ; to samo dotyczy wykresu, na którym niektóre z tych kopii dzielą jeden wierzchołek, tak że bloki wykresu mają lub . Wynika to z wyników w: J. Battle, F. Harary, Y. Kodama i JWT Youngs, „Additive of the graph of the graph”, Bull. Amer. Matematyka Soc. 68 (1962) 565–568 i już wystarczy, aby wykazać, że istnieje co najmniej wykładniczo wiele zakazanych nieletnich. $n$ $K_5$ $K_{3,3}$ $n-1$ $K_5$ $K_{3,3}$

Bojan Mohar, „Przeszkoda we osadzaniu grafów w powierzchniach”, Discrete Math. 78 (1989) 135–142, wymienia wykres utworzony z przez usunięcie 4-cykli jako mających rodzaj 2. Ponieważ jest toroidalny, oznacza to, że lub jeden z jego obejmujących podgraphów jest przeszkodą do osadzania torusa, a te wykresy, które mają kopii tego wykresu, ponieważ ich bloki mają rodzaj . $K_8$ $K_7$ $K_8\setminus C_4$ $n$ $2n$

Mohar pokazuje również, że wykres utworzony z cyklu poprzez połączenie wierzchołka 0 ze wszystkimi wierzchołkami parzystymi i wierzchołek 1 ze wszystkimi nieparzystymi wierzchołkami ma „rodzaj względny” co najmniej . Wykres jest płaski, ale myślę, że względny rodzaj oznacza, że cykl musi być twarzą; lub możesz dodać kolejny wierzchołek do wykresu, połączony ze wszystkimi wierzchołkami cyklu, aby skutecznie zmusić go do bycia twarzą. Być może jest to coś, czego chcesz. Ale nie sądzę, że pokazuje, że te wykresy są minimalnie zabronionymi nieletnimi. $(2k+2)$ $\lceil k/2\rceil$

David Eppstein
źródło

Twój ostatni akapit o cyklu

jest tym, czego szukam. Dzięki. Przyjmuję twoją odpowiedź.

(2 k + 2)

$(2k+2)$

Shiva Kintali