Noticias en español
Condiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados.
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 MoreReconocimiento y caracterización de cuadrados exactos de grafos.
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 MoreConversaciones entre la teoría de modelos y la teoría de grafos (tercera parte).
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 MoreConversaciones entre la teoría de modelos y la teoría de grafos (segunda parte).
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 MoreConversaciones entre la teoría de modelos y la teoría de grafos.
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 MoreComplexity of k-coloring (subdivided claw)-free graphs with bounded diameter.
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