Menores prohibidos para gráficos de género acotado

Es bien sabido que y son menores prohibidos para gráficos planos. Hay cientos de menores prohibidos para gráficos incrustados en un toro. El número de menores prohibidos para gráficos incrustados en la superficie del género g es una función exponencial de g . Mi pregunta es la siguiente: $K_5$ $K_{3,3}$

¿Hay un gráfico explícito en t vértices (que no es un gráfico completo) tal que sea un menor prohibido para gráficos incrustados en la superficie del género g , donde t es una función de g ? $G_t$ $G_t$

EDITAR: me di cuenta de que se conoce el siguiente teorema:

Para cada superficie Σ existe un número entero r tal que no se incrusta en Σ. $K_{3,r}$

Entonces, estoy buscando que no sea un gráfico completo, no un gráfico bipartito completo. $G_t$

graph-theory co.combinatorics graph-minor algebraic-topology Shiva Kintali
fuente

Entonces, ¿desea una familia de gráficos infinitamente parametrizada y bien construida (que no sean gráficos completos) que estén prohibidos para las superficies de todos los géneros?

Derrick Stolee

@Derrick. Si. Precisamente.

Shiva Kintali el

Luego, volvería a formular la pregunta usando esos términos: "¿Hay una familia de gráficos (simple de construir) para que sea un mínimo prohibido mínimo para gráficos incrustables en un género superficie? "

{H_{g} : g \geq 1}

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

H_{g} ≇ K_{n}

$H_g \not\cong K_n$

g

$g$

Derrick Stolee

La " y no son menores de " no puede ser lo que desea. Si no son menores de , entonces es plano y no puede ser un menor prohibido para ningún género superior.

K_{5}

$K_5$

K_{3, 3}

$K_{3,3}$

G

$G$

G

$G$

G

$G$

David Eppstein el

@DavidEppstein Eliminé mis modificaciones. Esencialmente, estoy buscando obstrucciones que sean "diferentes" de y .

K_{5}

$K_5$

K_{33}

$K_{33}$

Shiva Kintali el

Respuestas:

La unión disjunta de copias de (o ) es un mínimo prohibido mínimo para las gráficas del género ; Lo mismo es cierto para un gráfico en el que algunas de estas copias comparten un solo vértice, de modo que los bloques del gráfico son o . Esto se desprende de los resultados en J. Battle, F. Harary, Y. Kodama y JWT Youngs, "Aditividad del género de un gráfico", Bull. Amer Matemáticas. Soc. 68 (1962) 565–568, y ya es suficiente para demostrar que hay al menos exponencialmente muchos menores prohibidos. $n$ $K_5$ $K_{3,3}$ $n-1$ $K_5$ $K_{3,3}$

Bojan Mohar, "Una obstrucción para incrustar gráficos en superficies", Matemática discreta. 78 (1989) 135–142, enumera el gráfico formado a partir de al eliminar un ciclo de 4 que tiene género 2. Dado que es toroidal, esto significa que o una de sus abarcan es una obstrucción para incrustar torus, y que los gráficos que tienen copias de este gráfico como sus bloques tienen el género . $K_8$ $K_7$ $K_8\setminus C_4$ $n$ $2n$

Mohar también muestra que el gráfico formado a partir de un ciclo conectando el vértice 0 a todos los vértices pares y el vértice 1 a todos los vértices impares tiene "género relativo" al menos . El gráfico es plano, pero creo que el género relativo significa que el ciclo tiene que ser una cara; o podría agregar otro vértice al gráfico, conectado a todos los vértices del ciclo, para forzarlo efectivamente a ser una cara. Tal vez esto esté más cerca del tipo de cosas que quieres. Pero no creo que muestre que estos gráficos son menores prohibidos. $(2k+2)$ $\lceil k/2\rceil$

David Eppstein
fuente

Su último párrafo sobre el ciclo

es lo que estoy buscando. Gracias. Estoy aceptando tu respuesta.

(2 k + 2)

$(2k+2)$

Shiva Kintali