Seminario de Grafos

Condiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados.

Event Date: Jun 08, 2023 in Seminario de Grafos, Seminars

 Abstract: Diremos que un grafo $G$ apunta a un grafo $H$ si es que en cada $2$-arista-coloreo de $G$ existe una copia monocromática de $H$. Schelp tenía la idea de que si el grafo completo $K_n$ apunta un grafo pequeño $H$, entonces cada subgrafo denso de $K_n$ también apunta a H.

Read More

Reconocimiento y caracterización de cuadrados exactos de grafos.

Event Date: Jun 01, 2023 in Seminario de Grafos, Seminars

Abstract: Para un grafo G=(V,E) se define su cuadrado exacto, G^{[#2]}, como el grafocon el mismo conjunto de vértices V en donde una arista uv está en el cuadrado exacto si y solo si u y v están a distancia 2 en el grafo original G. Se dice que G es una raíz (cuadrada) exacta de G^{[#2]}. Se mostrará una caracterización de los grafos que tienen raíz exacta, donde dicha caracterización permite fácilmente crear un algoritmo de reconocimiento en tiempo polinomial. Se mostrará que reconocer grafos que tienen una raíz exacta que es bipartita es un problema NP-completo. Se presentará una...

Read More

Conversaciones entre la teoría de modelos y la teoría de grafos (tercera parte).

Event Date: May 25, 2023 in Seminario de Grafos, Seminars

Abstract: En esta charla se pretende mostrar la utilidad de la teoría de modelos en combinatoria. En concreto, en la obtención de resultados para grafos infinitos. Se comenzará introduciendo el concepto de modelo para un lenguaje con una signatura dada, el concepto de submodelo y submodelo elemental, subrayando sus diferencias mediante un ejemplo. Posteriormente, se expondrá la construcción de submodelos elementales como herramienta para obtener resultados en grafos infinitos, en concreto para mostrar que si un grafo no tiene ningún corte mínimo impar, y pertenece a un modelo M para el cual...

Read More

Conversaciones entre la teoría de modelos y la teoría de grafos (segunda parte).

Event Date: May 18, 2023 in Seminario de Grafos, Seminars

Abstract: En esta charla se pretende mostrar la utilidad de la teoría de modelos en combinatoria. En concreto, en la obtención de resultados para grafos infinitos. Se comenzará introduciendo el concepto de modelo para un lenguaje con una signatura dada, el concepto de submodelo y submodelo elemental, subrayando sus diferencias mediante un ejemplo. Posteriormente, se expondrá la construcción de submodelos elementales como herramienta para obtener resultados en grafos infinitos, en concreto para mostrar que si un grafo no tiene ningún corte mínimo impar, y pertenece a un modelo M para el cual...

Read More

Conversaciones entre la teoría de modelos y la teoría de grafos.

Event Date: May 11, 2023 in Seminario de Grafos, Seminars

Abstract: En esta charla se pretende mostrar la utilidad de la teoría de modelos en combinatoria. En concreto, en la obtención de resultados para grafos infinitos. Se comenzará introduciendo el concepto de modelo para un lenguaje con una signatura dada, el concepto de submodelo y submodelo elemental, subrayando sus diferencias mediante un ejemplo. Posteriormente, se expondrá la construcción de submodelos elementales como herramienta para obtener resultados en grafos infinitos, en concreto para mostrar que si un grafo no tiene ningún corte mínimo impar, y pertenece a un modelo M para el cual...

Read More

Complexity of k-coloring (subdivided claw)-free graphs with bounded diameter.

Event Date: Apr 27, 2023 in Seminario de Grafos, Seminars

Abstract: During the last decades, there has been a lot of research on the computational complexity of k-coloring in H- free graphs when H is a linear forest. It is known that  k-coloring $K_{1,3}$ (claw) free graphs is NP-complete for $k\geq 3$.In this talk, we will study the techniques used by Barnaby Martin, Daniël Paulusma and Siani Smith in 2021 to generalize this result for $K^{r}_{1,3}$ (subdivided claw) free graphs with bounded diameter.

Read More