Sesión Matemática DiscretaSubdivisiones impares en grafos de Kneser
Adrian Pastine
Departamento de Matemática, Universidad Nacional de San Luis, e IMASL (UNSL-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo $G$ decimos que contiene otro grafo $H$ como un menor si podemos obtener $H$ a partir de $G$ si se lo puede obtener del mismo por medio repetidas aplicaciones de tres operaciones: el borrado de vértices, el borrado de aristas, y la contracción de aristas. La conjetura más importante en el estudio de menores es la conjetura de Hadwiger, que dice que todo grafo $G$ contiene a $K_{\chi(G)}$ como un menor (donde $\chi(G)$ es el número cromático de $G$).
Por otro lado, decimos que $G$ contiene una inmersión de $H$ si se puede obtener $H$ a partir de $G$ por medio de la repetida aplicación de: borrado de vértices, borrado de aristas, y reemplazo de un par de aristas incidentes $\{u,v\}$ y $\{v,w\}$ por la arista $\{u,w\}$. De manera similar a lo que ocurre con el problema de menores, la conjetura de Abu-Khzam y Langston dice que todo grafo $G$ contiene una inmersión de $K_{\chi(G)}$.
Ambos problemas son generalizados en el estudio de subdivisiones. Una subdivisión de una arista $\{u,v\}$ se obtiene al agregar un nuevo vértice, $w$, y al reemplazar la arista $\{u,v\}$ por las aristas $\{u,w\}$ y $\{w,v\}$. Decimos que un grafo $G$ contiene una subdivisión de un grafo $H$ si se puede obtener un subgrafo de $G$ a partir de $H$ por medio de repetidas subdivisiones de aristas. Claramente, si un grafo $G$ contiene una subdivisión de $H$, entonces contiene una inmersión de $H$, y contiene a $H$ como un menor. Por lo tanto, el estudio de subdivisiones abarca tanto el problema de menores como el problema de inmersiones.
El problema de subdivisiones se restringe un poco más al concentrarnos en la versión impar del problema. Esto es que si dos vértices $\{u,v\}$ son vecinos en $H$, entonces el camino de $G$ obtenido a partir de las subdivisiones entre $u$ y $v$ debe tener una cantidad impar de aristas (existen también versiones impares del problema de menores y del problema de inmersiones). Esta restricción es interesante ya que un grafo bipartito completo contiene subdivisiones de grafos completos de un gran número de vértices, pero no contienen subdiviones impares de $K_3$. Así, el caso impar representa un poco mejor el número de coloreo.
El grafo de Kneser $K(n,k)$ tiene como vértices los subconjuntos de cardinalidad $k$ de un subconjunto base de cardinalidad $n$, y tiene aristas entre dos vértices si son disjuntos. En este trabajos estudiamos subdivisiones impares del grafo de Kneser, y demostramos que si $G=K(n,k)$, entonces $G$ tiene una subdivisión impar de $K_{\chi(G)}$.