Seminario de Grafos

Número cromático de grafos de distancia exacta.

Event Date: Sep 29, 2022 in Seminario de Grafos, Seminars

Abstract: Se presentarán los principales resultados del paper “Chromatic numbers of exact distance graphs” (https://doi.org/10.1016/j.jctb.2018.05.007) El grafo de distancia exacta p de un grafo G=(V,E) es el grafo con el mismo conjunto de vértices que G y entre dos vértices hay una arista si y sólo si estos vértices están a distancia exactamente p en G. Usando la noción de números de coloreos generalizados se encontrarán cotas para el número cromático de grafos de distancia exacta p, separando los casos en que p sea impar y el caso en que es...

Read More

Árboles generadores en grafos densos III.

Event Date: Sep 01, 2022 in Seminario de Grafos, Seminars

Abstract: En este seminario seguimos estudiando el artículo Spanning trees in dense directed graphs de Kathapurkar y Montgomery. Más específicamente, veremos cómo encontrar copias de algunos árboles casi-generadores en grafos densos. Además, vamos a ver como el Lema de Regularidad, utilizado en la demostración de otros resultados en el área, es reemplazado por un proceso aleatorio para encontrar la copia del árbol.

Read More

Árboles generadores en grafos densos II.

Event Date: Aug 25, 2022 in Seminario de Grafos, Seminars

Abstract: En el último seminario vimos un resultado de Komlós, Sárközy y Szemerédi de 1995 sobre la existencia de árboles generadores de grado máximo acotado en grafos densos. Este resultado fue mejorado en 2001 por los mismos autores, quienes demostraron que se puede encontrar árboles generadores de grado máximo O(n/log n) en grafos densos.   Recientemente, Kathapurkar y Montgomery presentaron una generalización de este resultado para grafos dirigidos. A diferencia de los resultados anteriores, la demostración de esta generalización no utiliza el Lema de Regularidad. En este seminario...

Read More

Árboles generadores en grafos densos I.

Event Date: Aug 18, 2022 in Seminario de Grafos, Seminars

Abstract: Dados dos grafos H y G un problema central en teoría de grafos extremales es determinar condiciones globales en G que garantizan la existencia de una copia de H en G. Un ejemplo de resultado en esa dirección es el Teorema de Dirac, que afirma que si G es un grafo en nvértices con grado mínimo al menos n/2, entonces existe una copia del ciclo en n vértices en G. En este seminario vamos a estudiar la relación entre el grado mínimo de G y la existencia de copias de diferentes árboles generadores de G. Más específicamente, vamos a ver el...

Read More

Coloreos no-repetitivos de grafos con treewidth acotado.

Event Date: Nov 29, 2021 in Seminario de Grafos, Seminars

Read More

Diversos resultados en covers monocromáticos.

Event Date: Nov 22, 2021 in Seminario de Grafos, Seminars

Abstract: En este seminario veremos algunos resultados bajo distintas condiciones sobre covers monocromáticos extraídos del artículo ( https://arxiv.org/pdf/2009.07239.pdf ). Entre las condiciones a presentar se encuentran restricciones en los colores, subgrafos de diámetro acotado, entre otros.

Read More